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

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

• Спочатку обчислити зважену суму входових даних від інших нейронів (плюс зсув).
• Тоді видати 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

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

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

Теорема

Нехай $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$.

Ряди

Теорема (Про розкладення в ряд Лорана)

Якщо $f:U\to\mathbb{C}$ аналітична і $\{r < |z-z_0|< R\} \subset U$, тоді $f$ можна розкласти в ряд Лорана: $$f(z) = \sum_{k=-\infty}^{\infty}a_k(z-z_0)^k,$$ який збігається в кожній точці кільця і збігається абсолютно і рівномірно в кожному підкільці $\{s\le |z-z_0|\le t\}$, де $ r < s < t < R $.

Теорема

Якщо $f$ аналітична в $\{r < |z-z_0| < R\}$, тоді $$f(z) = \sum_{k=-\infty}^{\infty}a_k(z-z_0)^k,$$ де $$a_k = \frac{1}{2\pi i}\int_{|z-z_0|=s}\frac{f(z)}{(z-z_0)^{k+1}}dz$$ для будь-якого $s$ між $r$ і $R$ і всіх $k\in \mathbb{Z}$.

Це не видається дуже корисним для знаходження значень $a_k$, але це може допомогти оцінити значення деяких з них.

Означення

Точка $z_0$ - ізольована сингулярність $f$, якщо $f$ - аналітична в проколотому диску $\{0 < |z − z_0| < r\}$ з центром $z_0$.

Якщо $f$ має ізольовану сингулярність в $z_0$, тоді $f$ має розклад Лорана. Члени ряду з від'ємними степенями називаються головною частиною, а з додатніми - правильною частиною ряду. Можливі три типи поведінки:

1. Відсутність від'ємних сетепенів $z$: $f(z) = \frac{\cos z - 1}{z^2} = \frac{1}{z^2}\left(-\frac{z^2}{2!}+\frac{z^4}{4!}-+\cdots\right)$.
2. Скінченна кількість від'ємних степенів $z$: $f(z) = \frac{\cos z}{z^4} = \frac{1}{z^4}\left(1-\frac{z^2}{2!}+\frac{z^4}{4!}-+\cdots\right)$.
3. Нескінченна кількість від'ємних степенів $z$: $f(z) = \cos\left(\frac{1}{z}\right) = 1 - \frac{1}{2!} \frac{1}{z^2} + \frac{1}{4!}\frac{1}{z^4} - \frac{1}{6!}\frac{1}{z^6} +- \cdots$

Означення

Припустимо, що $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 \mathbb{C}$ існує послідовність $\{z_n\}$ із $z_n \to z_0$ така, що $f(z_n) \to 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).$$