Хайкин С. - Нейронные сети (778923), страница 71
Текст из файла (страница 71)
(5.2) Гиперплоскостгь задаваемая уравнением тг~~р(х) = О, описывает поверхность в <р-пространстве (те. в скрытом пространстве). Обратный образ этой поверхности, т.е. х: зяте(х) = О, (5.3) аон „х,,х„...х;, = О, Е (5.4) о<цйн«...*.<ть где х, — 1-й компонент входного вектора х, причем хо присвоено значение 1, чтобы придать уравнению однородную форму. Произведение элементов х, вектора х г-го порядка (те.
хохм... х;,) называется одночленам (пюпоппа1). Для входного про- странства размерности то сумма в (5.4) включает (т о — г)! то'г' определяет разделяющую поверхность (зерагайпд каг(асе) во входном пространстве. Рассмотрим естественный класс отображений, получаемый при использовании линейной комбинации произведений г координат вектора входного образа. Разделяющие поверхности, соответствующие такому отображению, называются рациональными многообразиями г-го порядка (г-бз огдег габона! чапе!у). Рациональное многообразие г-го порядка в пространстве размерности то описывается однородным уравнением т.-го порядка в координатах входного вектора х: 5.2.
Теорема Ковера о разделимости множеств 345 х х О. б) Рнс. 6.1. Трн примера е-раадепнмых днхотомнй дпя различных множеств нз пяти точек в двумерном пространстве: линейно-разделимая дихотомия (а); сфернческн разделимая дихотомия (б); квадратнчно-разделимая дихотомия (в) в) одночленов. Примерами разделяющих поверхностей, описываемых уравнением (5.4), являются гиперплоскости ()турегр!апе) (рациональные многообразия первого порядка), квадрики (йпадпсе) (рациональные многообразия 2-го порядка) и гилерсферы ()турегзрЬеге) (квадрики с некоторыми линейными ограничениями на коэффициенты). Эти примеры показаны на рис.
5.1 для конфигурации из пяти точек в двумерном входном пространстве. В общем случае линейная разделимость предполагает сферическую разделимость, которая, в свою очередь, предполагает квадратичный вид классифицирующей функции. Обратное утверждение не всегда верно. В вероятностном эксперименте разделимость множества образов становится случайным событием, зависящим от выбранной дихотомии и распределения образов во входном пространстве. Предположим, что образы активации х„хз,..., хн выбираются независимо, в соответствии с вероятностным распределением, присущим входному пространству. Предположим также, что все возможные дихотомии Х = (х ),', равновероятны. Пусть Р(1т', тт) — вероятность того, что некоторая случайно выбранная дихотомия является кр-разделимой, если класс разделяющих гиперповерхностей имеет т1 степеней свободы. Согласно (219) можно утверждать, что (5.5) 346 Глава 5. Сети иа основе радиальных базисных функций где биномиальные коэффициенты, включающие ]У вЂ” 1 и т, для всех целых [ и т определяются следующей формулой: [([ — 1)...
([ — т + 1) т) т! Уравнение (5.5) отражает сущность теоремы Ковера о разделимости (Сечет'8 зерагаЬВ[(у (Ьеогет) случайных образов2. Это соотношение описывает совокупное биномиальное распределение, соответствующее вероятности того, что (М вЂ” 1) подбрасываний монетки приведет к выпадению не более (тт — 1) решек. Хотя поверхности скрытых элементов в уравнении (5.5) имеют полиномиальную форму и, следовательно, отличаются от тех, которые обычно используются в сетях на основе радиальных базисных функций, сущность этого выражения носит общий характер. В частности, чем выше размерность тг скрытого пространства, тем ближе вероятность Р([т', тг) к единице.
Подводя итог сказанному, следует отметить, что теорема Ковера о разделимости образов базируется на двух основных моментах. 1. Определение нелинейной скрытой функции (рг(х), где х — входной вектор, а т = 1, 2,...,тг. 2. Высокая размерность скрытого пространства по сравнению с размерностью входного. Эта размерность определяется значением, присваиваемым тг(т.е. количеством скрытых нейронов). Как утверждалось ранее, в общем случае преобразование сложной задачи классификации в пространство более высокой размерности повышает вероятность линейной разделимости образов.
Однако хочется подчеркнуть, что в некоторых случаях для обеспечения линейной разделимости достаточно нелинейного преобразования (п. 1) без повышения размерности пространства скрытых элементов. Это будет продемонстрировано на следующем примере. з Доказательство теоремы Хопера базируется иа следующих утверждениях [219]. ° теорема шлафяи (зсыайгв жеогепг), или меорена подсчета фунвгнй (йгпс1юп-сопл!!пй йпеогепг), которая утверждает, что количество однородных линейно-разделимых дихотомий )Ч векторов Евклидова гпгмерного пространства, находящихся в стандартном положении, определяется соотношением чг — Г С(а,гпг) = 2 2 ( ).
Говорят, что множество векторов Х = (х,)гг Евклидова пгг-мерного пространства находится в стандаршлон положении, если любое подмножество из шг или меньшего числа векторов является линейно- независимым. ° Рнбиексивлая инвариантност ь совместной вероятности распределения Х, которая означает, что вероятность (условнаа по Х) линейной разделимости случайной дихотомии равна безусловной вероятности толч что любая конкретная дихотомия множества Х (все 1Ч векторов находятся в одной категории) будет разделимой. теорема подсчета функций была независимо доказана в различных формах и применена к специальной конфигурации персептронов (те, линейных пороговых элементов) в [168], [528], [1!62].
В [218] зта теорема использовалась для оценки емкости сети персептронов в терминах общего количества настраиваемых параметРов. В статье было показано, что эта емкость огРаничена снизУ величиной )Ч,г(1-(-1ояз )Ч), где 1Ч вЂ” количество входных образов. 5.2. Теорема Хопера о разделимости множеств Зчу ТАБЛИЦА 5.1. Значения скрытых функций в задаче ХОР (см.
пример 5.1) Входной Первая скрытая функция, гр (х) Вторая скрытая функция, гр (х) образ, х (1;1) 1 0,1353 (О;1) 0,3678 0,3678 (О;0) 0,1353 1 (1;О) 0,3678 0,3678 Пример 5.1 Задача ХОК Чтобы проиллюстрировать значимость идеи е-разделимости образов, рассмотрим простую, но в то же время важную зш1ачу ХОК. В этой задаче в двумерном входном пространстве рассматриваютсв четыре точки; (О; 0), (О; 1), (1; 0) и (1; 1) (рис. 5.2, а).
Требуется построить твюй классификатор, который относит образы (О; 1) и (1; 0) к классу 1, в образы (О; 0) и (1; 1) — к классу О. Это значит, что ближайшие друг к другу точки во входном пространстве (в смысле расстояния Хеимннга (Напил(пй гйзгвпсе)) отображаются в области, которые максимально удалены друг от друга в выходном пространстве.
Определим пару гвуссовых функций следующим образом: ср,(х)=е ! 'г, Ц=(1, 1] <Рг(х) = е П И~1, Гг = (О, 0] Проаназизируем представленный в табл. 5.1 результат для четырех различных входных образов. Входные векторы отображаются нв плоскость е, — а, как показано на рис. 5.2, б.
На этом рисунке сразу видно, что теперь точки (О; 1) и (1; 0) стали линейно-отделимыми ст точек (О; 0) и (1; !). Следовательно, задачу ХОК можно успешно решить с помощью функций а,(х) и Е (х) для предварительной обработки входных данных линейного классификатора, такого квк персептрон. ° В этом примере ие повышается размерность скрытого пространства по сравнению с входным. Другими словами, нелинейного преобразования, представленного в данном случае двумя гауссовыми функциями, оказалось достаточно для трансформации задачи ХОК в линейно-разделимую задачу.
Разделяющая способность поверхности Уравнение (5.5) позволяет оценить максимальное количество случайно выбранных образов, линейно-разделимых в многомерном пространстве. Чтобы раскрыть этот вопрос, рассмотрим последовательность случайных векторов х„хг,..., хи. Пусть )т' — случайная переменная, определяемая как максимальное целое число, для котоРого эта последовательность Явлиетси 1Р-Разделимой, если гР имеет тг степеней 348 Глава б. Сети на основе радиальных базисных функций 1,0 0,8 О,б 02 0,4 0,2 (О, 1) (1, 1) (О, 0) (1, 0) ° ° 0 0,2 0,4 0,6 0,8 1,0 1,2 Ф) а) б) Рис. $.2.
Четыре образа для задачи ХОЙ (а) и диаграмма принятия решений (б) свободы. Тогда из соотношения (5.5) можно получить вероятность того, что )т' = п: Р(М = и) = Р(п,та) — Р(п+ 1, т,) = — п = О, 1, 2, (5.6) )(й;т,р) = р'а Для частного случая, когда р = д = 1,/2 (т.е. успех и ошибка равновероятны) и к + т = и, отрицательное биномиальное распределение сводится к виду Для интерпретации этого результата вспомним определение отрицательного биномиального распределения (пека(1)ге Ьзпоппа1 б(зпзЬп(юп). Это распределение определяет вероятность того, что т-му успешному эксперименту предшествует )О ошибок в длинной повторяющейся последовательности лолылаок Бернулли (Вегпоп111 (па1). В таком вероятностном эксперименте каждый результат может принимать одно из двух значений — успех или ошибка, — и их вероятности одинаковы на протяжении всего эксперимента. Пусть р и д — соответственно вероятности успеха и неудачи и р + д = 1.
Отрицательное биномиальное распределение имеет вид 1294) 5.3. Задача интерполяции 349 Учитывая это определение, несложно заметить, что результат, описанный выражением (5.6), является всего лишь отрицательным биномиальным распределением, смещенным на т| единиц вправо, с параметрами т, и 1/2. Таким образом, )У соответствует "времени ожидания" |и|-й ошибки в последовательности попыток подбрасывания монетки.
Ожидание случайной переменной Х и ее медиана (шеойап) соответственно равны Е[)У[ = 2гпд, Мейап[Х] = 2|п,. (5.7) (5.8) Таким образом, мы получили следствие из теоремы Ковера в форме асимптотического результата, который можно сформулировать следующим образом. Ожидаемое максимальное количество случайно задаваемых образов (векторов), линейно-разделимых в пространстве размерности пзп составляет 2тп 5.3. Задача интерполяции Важным выводом, следующим из теоремы Колера о разделимости образов, является то, что при решении нелинейной задачи классификации обычно имеется практическая польза от преобразования входного пространства в пространство более высокой размерности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
