Саймон Хайкин, Нейронные сети

[ihq.pl]

Здравствуйте! Новый год решил начать с изучения книги Саймона Хайкина "Нейронные сети. Машинное обучение" 3-е издание, и сразу загвоздка...

Пусть даны конечные множества $H_1 \subset \mathbb{R}^m$ и $H_2 \subset \mathbb{R}^m$, про которые известно, что они отделены друг от друга $(m-1)$-мерной плоскостью (linearly separable). Oбозначим

$$(\mathbf{w},\mathbf{x}) = w_0+w_1x_1+...+w_mx_m,$$

где $\mathbf{w} = (w_0,w_1,...,w_m),$ а $\mathbf{x} = (1,x_1,...,x_m)$. Нужно найти вектор $\mathbf{w}$ такой, что $(\mathbf{w},\mathbf{x})>0$ для всех $\mathbf{x}\in H_1$, и $(\mathbf{w},\mathbf{x}) \le 0$ для всех $\mathbf{x}\in H_2$.

Решение предлагают искать итеративно по следующему правилу. Полагаем $\mathbf{w}(0)=0$, а на шаге $n+1$ поступаем следующим образом:
1) если $\mathbf{x}(n)\in H_1$ и $(\mathbf{w}(n),\mathbf{x}(n))>0$, или $\mathbf{x}(n)\in H_2$ и $(\mathbf{w}(n),\mathbf{x}(n))\le 0$, то $\mathbf{w}(n+1) = \mathbf{w}(n)$;
2) если $\mathbf{x}(n)\in H_1$ и $(\mathbf{w}(n),\mathbf{x}(n))\le 0$, то $\mathbf{w}(n+1)=\mathbf{w}(n) + \mathbf{x}(n)$;
3) если $\mathbf{x}(n)\in H_2$ и $(\mathbf{w}(n),\mathbf{x}(n)) >0$, то $\mathbf{w}(n+1)=\mathbf{w}(n) - \mathbf{x}(n)$.
Назовем это правилом настройки перцептрона.

Утверждается, что по этому правилу решение находится за конечное кол-во шагов.
Док-во. Пусть для $\mathbf{x}(n)\in H_1, n=0,1,...$ выполнены неравенства $(\mathbf{w}(n),\mathbf{x}(n))\le 0$, где, в силу правила настройки перцептрона,

$$\mathbf{w}(n+1) = \mathbf{w}(n) + \mathbf{x}(n).$$

Известно, что решение существует (линейная отделимость мн-в). Oбозначим его через $\mathbf{w}$. Без ограничения общности можно считать, что Евклидова норма $\|\mathbf{w}\|=1$. Oпуская детали, просто скажу, что имеет место нер-во

$$n^2\alpha^2 \le \|\mathbf{w}(n+1)\|^2 \le n\beta^2,$$

которое, однако, верно только для $n\le\ n_m = \lfloor \beta^2/\alpha^2 \rfloor$. Здесь

$$\alpha = \min\limits_{\mathbf{x}\in H_1}(\mathbf{w}, \mathbf{x}), \quad\beta = \max\limits_{\mathbf{x}\in H_1}\|\mathbf{x}\|.$$

Всё! Этого, по мнению автора книги, достаточно для того, чтобы утверждать, что существует такое $n_0\le n_{m}$, что

$$\mathbf{w}(n_0) = \mathbf{w}(n_0+1) = \mathbf{w}(n_0+2) =.....$$

В общем, я в шоке. Либо надо начать изучать нейронные сети по другой книге, либо я чего-то не понимаю, и тогда прошу подсказать, где здесь собака зарыта. Заранее спасибо)

[ShMaxG]

Неравенство

$$n^2\alpha^2 \le \|\mathbf{w}(n+1)\|^2 \le n\beta^2,$$

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

[ihq.pl]

ShMaxG в сообщении #1545334 писал(а):

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

да, это я понимаю. Не вижу как из этого следует, что $\mathbf{w}(n_0)$ и есть искомый в-р. Чую, плохи мои дела(

[ShMaxG]

А по-моему в книге и не утверждается, что это будет искомый вектор. Ведь на самом деле плоскостей, отделяющих точки, может быть бесконечное множество, стало бы и этих векторов может быть столько же. Утверждается лишь, что процедура обязательно завершится, что с некоторого момента вектор весов устаканится. Заметьте, что в выделенном в книге утверждении именно в этом смысле и понимается сходимость (in the sense that...)

Ну, наверное просто еще не хватает слов про то, что считается, что $\alpha$ не 0, а $\beta$ не бесконечность, но это вроде бы и так понятно.

[ihq.pl]

ShMaxG в сообщении #1545363 писал(а):

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

Что решение не единственное, тоже понятно. Но то, что $\mathbf{w}(n_0)$ является решением (пусть даже только для $H_1$) - это вроде бы утверждается. Дословно из книги:

The perceptron converges after some $n_0$ iterations, in the sense that

$$\mathbf{w}(n_0) = \mathbf{w}(n_0+1) = \mathbf{w}(n_0+2) = ....$$

is a solution vector for $n_0\le n_m$.

[ShMaxG]

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

[ihq.pl]

ShMaxG, спасибо, попробую осмыслить это. А вообще, что вы скажете об этой книге, хорошая? Скачал просто первое из того, что скачивается на эту тему.

[ShMaxG]

Это классика, это читать полезно в любом случае. Хотя я ее читал не всю, меня интересовала в этой книге только часть про нейродинамику. Мне не понравилось, что он определяет нейронные сети как какие-то многопроцессорные системы, и введение в нейродинамику у него ужасное, какие-то электрические цепи. Он может думал, что инженерный взгляд на вещи поможет выработать интуицию, но в моем случае он промахнулся :) Я изучал машинное обучение по другой классике -- лекциям Andrew Ng из Стэнфорда и по разным современным книгам, а в эту заглядывал в частных случаях. Хотя у меня был студент, которому книга Хайкина очень сильно понравилась.

[Евгений Машеров]

Ну, что не единственная плоскость - уже сказали. И она ещё и не оптимальная. Какой-нибудь дискриминантный анализ сделает быстрее и лучше - но там надо найти ковариационную матрицу и обратить её. А тут рассматривается мозг или его модель, в которой умножение и деление не реализованы, а сложение и вычитание, в виде возбуждающих и тормозящих синапсов, есть. И ставится задача провести обучение при условии, что доступны только эти две операции (и оценка правильности классификации).
Сама процедура интуитивно ясна - при ошибке классификации разделяющую плоскость "пинают" в сторону уменьшения ошибки (возможно, недостаточно, чтобы полностью исключить ошибку классификации данного объекта, но, по крайней мере, даже если знак остался ошибочным, по абсолютной величине ошибка уменьшилась). И формального доказательства требует лишь то, что процедура когда-либо закончится, а не будет вечной. А оно приведено выше.

[ihq.pl]

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

$$w(n+1) = x(0)+....+x(n),$$

то

$$(w(n+1),x(k))>0$$

для $k=0,..,n$. Может, это и не архи сложно, но лично мне не очевидно. И если подобные недомолвки будут там на каждом шагу, то я прям не знаю...)

PS а так, мне кажется, я понял вашу мысль

[Евгений Машеров]

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