1 Линейная модель

В первом подразделе описывается линейная регрессия. Во втором основа нейронной сети – персептрон.

1.1 Линейная регрессия

Целью является приближение данных линейной функцией.

Линейной пространство Искомое параметрическое множество функций задается как $g\left(x,𝜃\right)={\sum }_{j=1}^{j=m}{𝜃}_j{e}_j\left(x\right)$, $𝜃=\left({𝜃}_1,...,{𝜃}_m\right)$. В качестве функций $e_j$ можно взять любые функции. Например $e_j\left(x\right)=x^{j-1}$ или $e_j\left(x\right)=sin\left(\left(j-1\right)x\right)$.

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

Также можно считать, что они с самого начала были выбраны экспертом при построении параметрического пространства, т.е. они есть суть функции $\phi$. В последнем случае уравнение сводится просто к линейной функции:

где $𝜃=\left({𝜃}_1,...,{𝜃}_m\right).$

Если подставить обучающее множество в исходное уравнение, то получим систему уравнений: $y_i={\sum }_{j=0}^{j=m}{𝜃}_j{e}_j\left(x_i\right)$. Замечу, что выражение $e_j\left(x_j\right)$ является числом, поэтому – это система линейных уравнений относительно параметров ${𝜃}_j$.

При определенных условия – что является предметом изучения курса по линейной алгебры – данная система имеет решение.

Если $m=n$, то это задача интерполяции. При интерполяции построенная функция $\tilde{f}$ проходит через исконное множество точек точно. т.е. функция качества будет равна $0$. Насколько это важно вопрос спорный. Может быть так, что как раз на тестовом множестве будет достигнут худший вариант.

Если взять $e_j\left(x\right)=x^j$, то получим задачу поиска многочлена проходящего через заданные точки. Вместо того, чтобы составлять систему уравнений и её решать, что подразумевает обращение матрицы – задача крайней неблагодарная – можно решить задачу иначе ... можно построить решение явным образом.

Например, используя интерполяционные многочлены Лагранжа. Положим $e_j\left(x\right)={\prod }_{k\ne j}\frac{x-x_k}{x_j-x_k}$, тогда она будет себя вести как индикаторная функция, а именно – при $j\ne i$ получим $e_j\left(x_i\right)=0$, в тоже время $e_j\left(x_j\right)=1$. Поэтому $𝜃=\left(y_1,...,y_n\right)$, т.е. $g\left(x,𝜃\right)=L\left(x\right)={\sum }_{j=0}^{m-1}{y}_j{e}_j\left(x\right)$.

Неудобна...

Формула Ньютона...

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

1.2 Аппроксимация

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

Двумерный случай Рассмотрим самый простой случай. Пусть $e_0\left(x\right)=a$, $e_1\left(x\right)=ax$, т.е. будем приближать данные линейной функцией. Причем, у нас один единственный признак ($n=1$). Данными являются пары числе ${\left(x_i,y_i\right)}_{i=1}^{i=l}$, где $x_i,y_i\in R$. С геометрической точки зрения это точки на плоскости.

В таком случае мы хотим минимизировать:

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

Пусть

и

Тогда

Следовательно

Дополнив выражение константами можно выделить полный квадрат относительно каждой из переменных. Последнее позволит минимизировать выражение относительно двух переменных.

Относительно $a$ (считаем $b$ константой):

Последнее означает, что если для параметра $b$ уже найдено оптимальное выражение, то $a$ нужно выбрать минимизировав данный квадрат, т.е. потребовав

По аналогии, относительно $b$ (считаем $a$ константой):

и соответственно:

Последние два требования сводятся к линейной системе

Решив систему, находим значения $a$ и $b$.

Общий случай Есть точки в $n$-мерном пространстве. Есть значение ассоциированное с каждой из точек. Необходимо построить линейную функцию приближающую эти данные.

На математическом языке, есть уравнение: $Ax=b\iff Ax-b=0.$ Хотим решить в среднеквадратичном смысле, т.е. минимизировать ${\left(Ax-b\right)}^T\left(Ax-b\right)=0.$

Напомним правило взятия производной у матриц....

Возьмем производную по $x$: $A^T\left(Ax-b\right)+A^T\left(Ax-b\right)=2C$, где $C=A^T\left(Ax-b\right).$ Тогда из равенства производной $0$ следует, что $2C=0\Leftarrow =C=0.$ Следовательно верно:

Тогда $x={\left(A^{T}A\right)}^{-1}{A}^{T}b$. Пусть $A^{+}={\left(A^{T}A\right)}^{-1}{A}^T$, искомый ответ представляется в виде $x=A^{+}b$. Напомню, что для обычных уравнений ответ записывается в виде: $x=A^{-1}b.$ В этом смысле матрица $A^{+}$ считается псевдо обратной к $A$.

Общий Сначала для общего случае. Тогда справедливо:

Если

то тогда описанный данный подход не применим. Нужно действовать иначе: градиент.

В более общем случае не получится:

1.3 Классификация

В первой лекции было указано, что признак соответствующий классам задаются конечным множеством элементов. Например: $\left\{1,...,N\right\}$. Такой подход неизбежно приводит к тому, что классы обрабатываются не равнозначно/равносильно. Так, $1$ самое маленькое число, а $N$ – большое. У крайних чисел чисел ($1$ и $N$) по одному непосредственному соседу, а у других чисел (классов) их $2$. Можно применить к классам операцию больше и меньше, в частности, можно выделить два суперкласса: $\left\{1...k\right\}$ и $\left\{k+1...N\right\}$, что опять же будет препятствовать честному обучению.

Итог. Лучше заменить данный признак на $N$ бинарных, каждый их которых способен отделить друг от друга только два класса. Фактически дать ответ на вопрос Да/Нет относительно принадлежности данному классу. Конечно может быть неоднозначность, когда два или более бинарных признаков дадут ответ Да.

Итого, классификация сводится к изучению бинарных классификаторов. Без ограничения общности, можно считать, что обучающая выборка будет содержать y из множества $\left\{1,-1\right\}$ и в соответствии с этим при $f\left(x\right)>0$ ответ Да, а при $f\left(x\right)<0$ ответ Нет. Тогда нетрудно видеть, что для правильно спрогнозированного ответа верно:$yf\left(x\right)>0.$

1.4 Персептрон

Модель: семейство функций и алгоритм поиска минимума. Из биологии.

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

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

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

Внутреннее устройство нейрона является черной коробкой, но считается крайне простым. Считается, что нейрон комбинируя входные нейроны выстреливает свой сигнал в выходное.

Обучение за счет соединений, точнее адаптации силы подсоединения к другим нейронам. В биологии все устроено сложнее, но нам это не важно как уже было сказано ранее.

Пусть мы решаем задачу бинаризации, т.е. задачу отделения одного множества объектов от другого. Для нас нейрон сводится к функции от $n$-переменных:

А в учитывая то, что мы хотим получить максимально простую функцию, то нет ничего проще линейной функции:

где $\omega =\left({\omega }_0,{\omega }_1,...,{\omega }_n\right)$ – параметр характеризующий функцию. Ответ нейрона мы будет интерпретировать знаком функции. В случае положительного знака считаем, что нейрон относит данный объект к + объектам, в случае отрицательного – к - объектам. При равенстве функции – считаем что имеет место неопределенность.

Для упрощения записи функции, можно считать, что например есть фиктивный признак ($x_0$) всегда равный $1$, тогда формулу можно записать в виде:

где последнее является скалярным произведением векторов $x=\left(x_0,x_1,...,x_n\right)$ и $\left({\omega }_0,{\omega }_1,...,{\omega }_n\right)$. Иногда будет использована такая форма для сокращения записи.

Семейство функций есть. Как же устроен алгоритм обучения. Их может быть много. Рассмотрим традиционный.

Как было уже написано выше, знак величины

определяет принадлежность к определенному классу. Если взять пример пары $\left(x^j,y^j\right)$, где $x^j$ – вектор признаков j-примера, а $y^j$ – ответ для j-примера (т.е. значение $+1$ или $-1$). Тогда согласно ранее описанному в случае, если персептрон не ошибается будет истинно:

Соответственно в случае ошибки, величина будет меньше или равна нулю. Тогда мы должны проверить персептрон на всех примерах данных (обучающая выборка), и если он даст правильный ответ то ничего не делать. А вот в случае ошибки потребуется некая модификация вектора $\omega$. В деталях последнего действия и заключается суть алгоритма. Для традиционного алгоритма она такова:

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

Покажем, что при таком обучении действительно можно ожидать настройки параметров под модель. Без ограничения общности можно считать, что нашим примером является $\left(x,1\right)$. Тогда $a<0$. Что будет если посчитать значение этого примера на обновленных параметрах? Будет следующее:

Последнее показывает, что $á$ увеличивается как минимум на $1$ относительно $a$. Поэтому есть шанс того, что оно может стать больше $0$ и тогда нейрон будет правильно классифицировать данный пример. Но конечно не ясно, какой будет результат давать нейрон при новых параметрах на других примерах, в частности тех, на которых ранее давался правильный ответ.

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

Пусть пока $w_0=0$. Рассмотрим некое $\omega =\left({\omega }_1,...,{\omega }_n\right)$. Построим множество $x=\left(x_1,...,x_n\right)$ов:

Учитывая, что ${\sum }_{i=1}^{i=n}{\omega }_i{x}_i$ есть $<w,x>$, и вспоминая смысл равенства скаляра $0$ следует, что множество $\mathcal{ℬ}$ состоит из векторов перпендикулярных вектору $\omega$:

В двумерном случае, $\mathcal{ℬ}$ есть вектор перпендикулярный вектору $\omega$, в трехмерном (как и выше) это уже называется плоскостью (гиперплоскостью).

Заметим, что $\mathcal{ℬ}\perp \omega \iff \mathcal{ℬ}\perp 2\omega$, т.е. определение множества $\mathcal{ℬ}$ не зависит от масштаба вектора $\omega$. Поэтому для определенности можно положить его норму равной 1:$\parallel \omega \parallel =1.$

Если $\parallel \omega \parallel =1$, то $a=<x,\omega >$ есть величина проекции вектора $x$ на $\omega$. Тогда все вектора $x$, в частности, все входные данные подвергаются данной проекции. Фактически мы строи новый признак равный некоторой взвешенной сумме имеющихся признаков. В таком случае задачу разделения двух множеств будет сводится к поиску точки раздела на оси $\omega$. Эта точка и задается величиной $w_0$.

Сходимость алгоритма Сходимость зависит от данных. Если в принципе такой разделяющей плоскости провести нельзя, то не алгоритм сойдется никогда.

Крайние случаи.

Пример 1. Признаков нет. Тогда можно менять только ${\omega }_0$, которая и будет задавать знак. Если все-таки объекты принадлежать к разным классам, то такое $b$, чтобы эти два класса разделить, подобрать не удасться.

Пример 2. Нельзя разделить прямой объекты:

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

Ясно, что если $X$ не разделима, то $\delta =-\infty$.

Теорема. Если $\delta >0$, $\forall x\in X\Rightarrow \parallel x\parallel \le 1,$ то предложенный ранее алгоритм сойдется за не более чем за $\frac{1}{{\delta }^2}$ обновлений.

Док-во. Раз $\delta >0$, то $\exists x^{\ast }$ и ${\omega }^{\ast }$, которые реализуют $\delta$, т.е.

Пусть ${\omega }^{\left(0\right)}$ начальное значение вектора параметра итерационного процесса алгоритма. Тогда на $k$ шаге раз $w^{\left(k\right)}$ обновили, то была ошибка на прошлом шаге на неком примере $x$, т.е. $y<w^{\left(k-1\right)},x><0$. По построению алгоритма $w^{\left(k\right)}=w^{\left(k-1\right)}+yx$. Вычислим

т.е. проекция вектора $w^k$ на правильный вектор постепенно увеличивается:

Теперь необходимо понять вектор $w^{\left(k\right)}$ увеличивает свой размер вдоль вектора $w^{\ast }$ или нет. Для этого оценим скорость роста самого вектора $\parallel {\omega }^{\left(k\right)}\parallel .$

учитывая, что $\left|y\right|=1$, $\parallel x\parallel \le 1$ и вспоминая, что $y<{\omega }^{\left(k-1\right)},x><0$:

Откуда $\parallel {\omega }^{\left(k\right)}{\parallel }^2\le k.$

Тогда

Откуда $\sqrt{k}\ge k\delta$. Следовательно $k\le \frac{1}{{\delta }^2}.$ ЧТД.