Пользователь
0,0
рейтинг
21 марта 2012 в 05:09

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

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

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



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

Итак, первое что нам нужно знать это, что такое А-матрица перцептрона и 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. Но чтобы ускорить процесс схождения, можно получить больший уровень хаоса в матрице А. Как это сделать — нам как раз расказывает криптография. Вот такая связь с криптографией тут еще нарисовалась.
Сергей @tac
карма
–15,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (54)

  • +1
    Гм…

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

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

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

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

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

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

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

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

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

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