Какова роль первого «случайного» слоя в перцептроне Розенблатта

    Итак в статье Перцептрон Розенблатта — что забыто и придумано историей? в принципе как и ожидалось всплыло некоторая не осведомленность о сути перцептрона Розенблатта (у кого-то больше, у кого-то меньше). Но честно говоря я думал будет хуже. Поэтому для тех кто умеет и хочет слушать я обещал написать как так получается, что случайные связи в первом слое выполняют такую сложную задачу отображения не сепарабельного (линейно не разделимого) представления задачи в сепарабельное (линейно разделимое).

    Честно говоря, я мог сослаться просто на теорему сходимости Розенблатта, но так как сам не люблю когда меня «посылают в гугл», то давайте разбираться. Но я исхожу из-то, что Вы знаете по подлинникам, что такое перцептрон Розенблатта (хотя проблемы в понимании всплыли, но я все же надеюсь что только у отдельных людей).



    Начнем с матчасти

    Итак, первое что нам нужно знать это, что такое А-матрица перцептрона и G-матрица перцептрона. Дам ссылки на википедию, писал сам поэтому доверять можно (прямо из оригинала):
    1. А-матрица перцептрона
    2. G-матрица перцептрона, тут надо обратить внимание на Связь А и G — матриц перцептрона

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

    Далее поговорим о теории сходимости перцептрона. О ней много говорят, но уверен 50% её в глаза не видели.

    Итак, из одной моей научной статьи:

    Была доказана следующая теорема:

    «''Теорема 3.'' Даны элементарный перцептрон, пространство стимулов W и какая-то классификация C(W). Тогда для существования решения необходимо и достаточно, чтобы существовал некоторый вектор u, лежащий в том же ортанте, что и C(W), и некоторый вектор x, такой, что Gx=u .»

    а также два прямых следствия из этой теоремы:

    «''Следствие 1.'' Даны элементарный перцептрон и пространство стимулов W. Тогда, если G — особенная матрица (детерминант которой равен нулю), то имеется некоторая классификация C(W), для которой решения не существует.»

    «''Следствие 2.'' Если число стимулов в пространстве W больше числа А – элементов элементарного перцептрона, то существует некоторая классификация C(W), для которой решения не существует».

    Пространством стимулов Розенблатт называет пространство исходных данных.


    Доказательства я естественно рассматривать не буду (см. оригинал), но что нам далее будет важно — схождение перцептрона математически не гарантируется (не гарантируется не означает не будет — при простых входных данных будет, даже если нарушить, речь идет именно о произвольных входных данных) в двух случаях:
    1. Если число примеров в обучающей выборке будет больше чем число нейронов в среднем слое (А-элементов)
    2. Если у G матрицы детерминант равен нулю

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

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

    И теперь мы переходим к вопросу:
    Но так как первый слой связей в перцептроне выбирается случайным образом и не обучается, часто возникает мнение, что с равной вероятностью перцептрон может работать, а может не работать при линейно неразделимых исходных данных, и только линейные исходные данные гарантируют его безупречную работу. Другими словами, — матрица перцептрона с равной вероятностью может быть как особенной, так и не особенной. Здесь будет показано, что такое мнение ошибочно. (тут и далее, цитаты из моих научных статей)


    Вероятность активности А – элементов

    Из определения матрицы А видим, что она бинарная, и принимает значение 1, когда активен соответствующий А – элемент. Нас будет интересовать, какова вероятность появления в матрице единицы и, соответственно, какова вероятность нуля.


    Дальше я немного пропущу детали и дам сразу рисунок:


    это т.н. Q-функции проанализированные Розенблаттом. В детали я вдаваться не буду, но тут важно, что:

    x это число возбуждающих связей в первом слое, подходящие к одному А-элементу (вес +1) и y число тормозящих (вес -1). По оси y на рисунке показана величина этой Q-функции, которая зависит от относительного числа освещенных элементов на сетчатке (1 на входе).

    На рисунке показана зависимость вероятности активности А — элемента Qi от величины освещенной площадки сетчатки. Заметим, что для моделей, у которых имеются только возбуждающие связи (y=0) при высоком числе освещенных S — элементов значение Qi приближается к 1. То есть вероятность активности А – элементов находится в прямой зависимости от числа освещенных S — элементов, что плохо влияет на распознавание относительно малых и больших изображений. Как будет показано ниже, это происходит из-за большой вероятности того, что А – матрица будет особенной. Поэтому для стабильности распознавания образов любых геометрических размеров надо так выбрать отношение x:y, чтобы вероятность активности А – элементов как можно меньше бы зависела от числа освещенных S -элементов.

    … видно, что при x=y значение Qi остается примерно постоянной во всей области, за исключением очень малого или очень большого числа освещенных S — элементов. А если увеличить общее число связей, то область, в которой Qi остается постоянной, расширяется. При малом пороге и равных x и y приближается к значению 0.5, т.е. равно вероятному возникновению активности А – элемента на произвольный стимул. Таким образом, найдены условия, при которых появление единицы и нуля в матрице А равновероятно.


    А этом случае число единиц в матрице А будет описываться биномиальным распределением. Для примера, на следующем рисунке показано распределение числа матриц N в зависимости от количества единиц n в матрице, размером 5х5



    И наконец, какова вероятность того, что А матрица особенная?

    Из биноминального распределения можно узнать, как распределено общее число матриц с разным числом единиц в матрице (верхняя кривая на предыдущем рисунке). Но для числа неособенных матриц (нижняя кривая на предыдущем рисунке) математической формулы на данный момент не существует.
    Но есть последовательность А055165 [6], дающая вероятность именно того, что матрица размером n x n не особенная. Но посчитать ее можно лишь перебором и это сделано до случаев n <=8. Но последующие значения можно получить методом Монте-Карло…


    И вот что получается видно на следующем рисунке (это вероятности появления не особенных матриц в зависимости от их размера):



    Итак, отсюда видно, что уже при размере матрицы 30 x 30 (т.е. когда число А-элементов 30 и больше) можно говорить почти о 100% уверенности, что случайно полученная матрица будет не особенная. Это и является тем окончательным практическим условием, при котором перцептрон Розенблатта будет формировать пространство, удовлетворяющее гипотезе компактности. Практически же надежнее иметь минимум порядка 100 А-элементов для исключения случая, когда G-матрица становится особенной.

    И в заключение. А теперь задайтесь вопросом: а гарантирует ли MLP+BackProp, то о чем я вам здесь изложил в отношении перцептрона Розенблатта? Убедительных доказательств этому я нигде не нашел (только не кидайте ссылки на мат. доказательства сходимости градиентного спуска — это к этому не относится, лучше всего моим оппонентам советую написать свою вразумительную статью на этот счет: "на Хабрахабре приветствуются мысли из своей головы" — будет конструктивнее). Но исходя из наличия проблемы попадания в локальные минимумы при использовании BackProp — тут похоже не все чисто и гладко, как с перцептроном Розенблатта.

    upd. что я несколько упустил из вида в изложении, и в ходе диалога мы тут уточнили. Спасибо retran и justserega за наводящие вопросы.

    Резюме. В следствиях 1 и 2, говорится, что в определенных условиях решение невозможно. Тут я доказал, что такие условия при n > 30 не наступают (Розенблатт этим не занимался). Но у читателей возникло два вопроса

    1. Хорошо А-матрица (а через неё и G) пригодна с высокой вероятностью. Но как это помогает перейти в другое пространство?. Действительно, не очень очевидно. Поясняю. А-матрица это и есть «другое пространство» — пространство признаков. Факт того, что матрица не является особенной и эта матрица на одну размерность больше чем исходная — и есть признак того, что она может быть разделена линейно. (это следует из следствий и теоремы 3)

    2. "есть ли доказательства, что алгоритм коррекции ошибки в перцептроне Розенблатта сойдется?". Действительно, теорема №3 говорит только о том, что решение существует. Это уже означает, что это решение существует в пространстве признаков, т.е. после работы случайного первого слоя. Алгоритм же коррекции ошибки обучает второй слой, и существует у Розенблатта теорема №4, в которой он доказывает, что существующие возможные решения (теорема 3, что они вообще есть) могут быть достигнуты именно при применении алгоритма обучения с коррекцией ошибки.

    Еще важный момент следует из того, что А-матрица зависит с одной стороны от входных данных, а с другой от случайной матрицы связей. Точнее происходит отображение входной матрицы в матрицу А через случайный оператор (образованные случайно связи ). Если ввести меру случайности, как скорость появления подпоследовательностей которые будут повторяться (псевдослучайность), то окажется: (1) если это совсем не случайная, а построенный по некоторым правилам оператор (т.е. соединения первого слоя), то существенно возрастает вероятность получить А-матрицу особенной (2) если же после умножения входной матрицы на полученную нами псевдослучайность А-матрица имеет не регулярный, а хаотический разброс единиц (назовем это условие R) — то это как раз то, что выше мы в статье анализировали.

    Здесь я вам открою мною опробованную вещь. По идеи биномиальной модели случайности при создании связей (это когда берется А-элемент и от него случайно проводятся N возбуждающих и M тормозяцих связей к S-элементам) достаточно, чтобы выполнить условие R. Но чтобы ускорить процесс схождения, можно получить больший уровень хаоса в матрице А. Как это сделать — нам как раз расказывает криптография. Вот такая связь с криптографией тут еще нарисовалась.
    Метки:
    Поделиться публикацией
    Комментарии 54
    • +1
      Гм…

      Ну хорошо, показали, что G-матрица валидна с высокой вероятностью.
      Вот только как это помогает перейти в другое пространство?

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

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

      Где я не прав?
      • +1
        Тогда получается, что имея некую заданную обучающую выборку, веса надо назначать не случайно, а как раз под эту конкретную обучающую выборку.

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

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

        Но это важно на практике и известно как с этим бороться. По сути достаточно компьютерного генератора случайности, но можно сделать лучше — от этого будет лишь зависеть скорость схождения. Но схождение будет гарантировано.
        • –1
          Где доказательства, что схождение будет гарантировано? Максимум, что вы доказали в этой статье, что оно не невозможно.
          • +1
            Доказательства см. в теореме схождения Розенблатта.
            • –1
              Как бы ожидалось их здесь увидеть, на протяжении всей статьи было рассказано только о том, что результирующая матрица будет иметь обратную… и что дальше-то?
              • +1
                а этого и достаточно, см. следствия 1 и 2 теоремы схождения
              • +1
                Я исходил из того, что она доказана и доказаны используемые два следствия. Если найдете у Розенблатта в доказательстве ошибки — продолжим разговор.
                • –2
                  Слив засчитан. В следствиях говорится о несуществовании решения. То, что в определенных условиях решения не существует, не следует, что в других оно существует… И уж точно из этого не следует, что алгоритм к нему сойдется…
                  • 0
                    Вы сами поняли что написали :(
                    • 0
                      а я понял, вы снова мою статью не читали
                      • 0
                        Я ваши статьи читаю на несколько раз =) А вот вы от конкретных вопросов увиливаете. Итак в следствиях, говорится, что в определенных условиях решение невозможно. Вы в статье доказали, что такие условия при больших n не наступают. Я правильно понял?
                        • 0
                          теперь да
                          • 0
                            Ок, мы исключили два условия в которых решения нет. А где доказательства, что алгоритм сойдется?
                            • 0
                              Это все у Розенблатта в полной мере — теорема 3 и 4.
                              • +7
                                Не могли бы вы это добавить в статью?
                  • 0
                    Проблема в том, что там либо нет, либо непонятно как происходит переход из одного пространства в другое, а доказывается только некая общая универсальная сходимость перцептронов. О чем я выше и спросил ;)

                    А во-вторых, теорема говорит, только о том, что перцептрон рано или поздно сойдется, а не то что он сойдется на данной конкретной конечной выборке из n элементов, если не начать ее прокручивать сначала, в случае если перцептрон не сошелся сразу.
                    • 0
                      Ну, это математика :) Там доказывается вообще и сказано, что чтобы сошлось надо выполнить два условия из следствий 1 и 2, я показал, что они выполняются.

                      Во-вторых, теорема 4 говорит существующие возможные решения (теорема 3, что они вообще есть) могут быть достигнуты именно при применении алгоритма обучения с коррекцией ошибки.
                      • 0
                        И да конечно, показывать все примеры из обучающей выборке, надо многократно — это по моему общеизвестно.
              • 0
                «Вот только как это помогает перейти в другое пространство?»

                А-матрица это и есть «другое пространство» — пространство признаков. И как я понимаю (настоящие математики меня могут поправить, если ошибаюсь), факт того, что матрица не является особенной и эта матрица на одну размерность больше чем исходная — и есть признак того, что она может быть разделена линейно.
                • 0
                  Я вот скачал Минского, там тоже есть эта теорема, только в другой формулировке и с двумя другими доказательствами похоже. Попробую разобраться вечером после работы, может подойду ближе к истине ;)
                  • 0
                    Там осторожно, Минский не очень аккуратен в формулировках, если поверхностно читать можно его понять превратно.
                • 0
                  А сравнивать с регрессионным подходом думаю не правомерно (хотя я в это не селен, и как раз хотел бы послушать от специалистов как там это происходит), но там другая ситуация — там поле не дискретно бинарное.
                  • +2
                    В двух словах:

                    Ищется система, т. н. линейных решающих функций вида:
                    d(X) = W*X (тот же нейрон в общем-то),
                    где X — вектор признаков, W — вектор весов.
                    Веса ищутся на основе обучающей выборки через оптимизацию среднеквадратичной ошибки выхода как правило градиентным спуском.

                    Переход от нелинейно разделимой задачи к линейно осуществляется через повышение степени решающей функции, т. е. вместо
                    d(X) = w1*x1 + w2*x2
                    используется что-то вроде
                    d(X) = w1*x1*x1 + w2*x1*x2 + w3*x2*x2

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

                    Ну и в многослойных перцептронах (там где я читал) поле абсолютно не обязательно дискретнобинарное.
                    • 0
                      Это в MLP не дискретнобинарное, оно там и не может быть принципиально таким. Я говорил, что в перцептроне Розенблатта оно обязательно дискретнобинарное.
                      • 0
                        Ок, это вы рассказали, что якобы сигмоид + градиентный спуск переводит нелинейное представление в линейное. А именно на месте этого

                        d(X) = w1*x1*x1 + w2*x1*x2 + w3*x2*x2

                        может быть сигмоид и это и есть гарантия перевода? Что-то я сомневаюсь. Но вначале подтвердите, что я правильно понял.
                        • 0
                          Да сигмоид может быть, только тогда эта будет сумма произведений разных сигмоидов от ВСЕГО вектора признаков и соответствующих весов.

                          Как сами сигмоиды должны выглядеть от вектора признаков сейчас не смогу сказать.
                          • 0
                            Тогда действительно, это вряд ли гарантирует 100% переход из нелинейного представления в линейное. В MLP не требуется иметь число нейронов в среднем слое равным числу примеров в обучающей выборке. Сколько их должно быть там ответ один — гадайте. Нелинейная функция активации, конечно несколько увеличивает размерность по сравнению с пороговой у Розенблатта, но во-первых гарантий нет, а во вторых, вычислительная стоимость нелинейной функции больше (это конечно сравнительно гасится большим числом нейронов у Розенблатта, но и только). Возможно, отсутствие аналога особенно А-матрицы, в MLP гарантируется просто не нулевыми начальными весами, и малой вероятностью, превращения их в нули. Но все это надо показывать аналогично тому, как я показал в своей статье на основании доказанного Розенблаттом.
                            • 0
                              www.machinelearning.ru/wiki/images/6/68/Voron-ML-Lin.pdf — вот тут на странице 27 про сигмоиды, а до этого про связь с перцептронами и многослойными сетями.
                              • 0
                                Но это же метод опорных векторов (SVM) — причем он тут?
                                • 0
                                  Оно почти так же выглядит и для градиентного спуска, который в данной статье идет в самом начале.
                                  • 0
                                    Так там как раз пример 1.5. и показывает как все плохо, в полном соответствии с моими сомнениями выше
                                    • 0
                                      Поясните, пожалуйста.
                                      • 0
                                        Я вот об этом

                                        Что плохого произойдёт, если функция K(u, v) не будет удовлетворять услови-
                                        ям Мерсера?… возникнет огромное количество локальных минимумов, и поиск решения среди них в общем случае потребует полного перебора. В этой ситуации многие методы квадратичного программирования будут выдавать
                                        какой-то локальный минимум, совсем не обязательно хороший.
                                        • 0
                                          А. Это не пример, это между примерами текст ;)
                                          А сама проблема локальных минимумов есть у всех методов оптимизации и машинного обучения, в том числе и у перцептронов.
                                          • 0
                                            Может оно и так, но я вот ни как не пойму — как же это должно отражаться на сходимости?
                                            • 0
                                              Если изменения весов слишком маленькие и константные, то алгоритм может зациклиться вокруг неправильного вектора весов.

                                              Я так понимаю, что ввод случайных изменений весов у Розенблатта — это как раз борьба с локальными минимумами.
                                              • 0
                                                Нету там ввода случайных изменений весов, я же писал, что это для особенной схемы без учителя.

                                                Так вот в том то и дело — нету у перцептрона Розенблатта даже намека, что алгоритм зациклится.
                          • 0
                            Да нет же, в логистической регрессии нет перевода в другое пространство… Логистическая регрессия — это по сути один нейрон, даже не слой, а именно один нейрон.
                              • 0
                                А поконкретнее? Что не так?
                                • 0
                                  Как бы там написано про перевод в другое пространство конкретно для регрессии. А раньше — про связь с нейронами и почему регрессия не обязательно один нейрон.

                                  Это я к тому, что вы в вашем комментарии не правы.
                                  • 0
                                    Для регрессии — ок. Но сама регрессия, не подразумевает переводов в другое пространство. Про количество нейронов — один точно один-в-один лог. регрессия… а больше, надо подумать… )
                                    • +1
                                      У вас не обязательно одна решающая функция. Это может быть система функций ;)
                                      • 0
                                        Вы совершенно правы. Упустил это из виду.
                    • 0
                      Вы очень много в статье говорили о своих научных статьях. Мне было бы интересно их почитать. Вы могди бы сказать их выходные данные?
                    • –1
                      Может вы напишете еще статью про алгоритм обучения с коррекцией ошибки? А то что-то не могу его найти.
                      Про случайный слой: это же гениально, согласен, без него, скорее всего вероятность схождения меньше(только догадки).
                      P.S. Далеко не все(в том числе и я) слышали, что есть перцептрон Розенблата, а читать 500 страниц уж очень долго.
                      • 0
                        Вот краткое описание метода коррекции ошибки. Получается, что у него после достижения весом нуля, он не может из него выйти, как и у обратного распространения.
                        • 0
                          Получается, что у него после достижения весом нуля, он не может из него выйти, как и у обратного распространения.

                          Это не верно. Там вообще обучение начинается с нулевых весов.
                          • 0
                            «Там вообще обучение начинается с нулевых весов» — а можно чуть подробнее? Как именно выходит из нуля?
                            • 0
                              Хорошо, я напишу позже статью об основах перцептрона Розенблатта, где этому уделю внимание

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.