Гауссова адаптация

Гауссова адаптация (ГА) , также называемая нормальной или естественной адаптацией (NA), представляет собой эволюционный алгоритм , предназначенный для максимизации производительности производства за счет статистического отклонения значений компонентов систем обработки сигналов . Короче говоря, ГА — это стохастический адаптивный процесс, в котором несколько выборок n -мерного вектора x [ x ^Т = ( x ₁ , x ₂ , ..., x _n )] берутся из многомерного гауссовского распределения N ( m , M ) , имеющего среднее значение m и матрицу моментов M . Образцы проверяются на провал или прохождение. Моменты первого и второго порядка гауссианы, ограниченной проходными выборками, равны m* и M* .

Результат x в качестве проходной выборки определяется функцией s ( x ), 0 < s ( x ) < q ≤ 1, так что s ( x ) — это вероятность того, что x будет выбран в качестве проходной выборки. Средняя вероятность обнаружения проходных проб (выход) равна

$P(m)=\int s(x)N(x-m)\,dx$

Тогда теорема ГА гласит:

Для любого s ( x ) и для любого значения P < q всегда существует гауссова PDF [ функция плотности вероятности ], адаптированная для максимальной дисперсии. Необходимыми условиями локального оптимума являются m = m * и M , пропорциональное M *. Также решается двойная задача: P максимизируется при сохранении постоянной дисперсии (Kjellström, 1991).

Доказательства теоремы можно найти в работах Кьельстрема, 1970 г. и Кьельстрема и Таксена, 1981 г.

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

Теорема справедлива для всех областей приемлемости и всех гауссовских распределений . Его можно использовать путем циклического повторения случайных изменений и отбора (подобно естественной эволюции). В каждом цикле достаточно большое количество точек, распределенных по Гауссу, отбирается и проверяется на принадлежность к области приемлемости. Центр тяжести гауссианы m затем перемещается в центр тяжести утвержденных (выбранных) точек m *. Таким образом, процесс сходится к состоянию равновесия, удовлетворяющему теореме. Решение всегда приближенное, поскольку центр тяжести всегда определяется для ограниченного числа точек.

Впервые он был использован в 1969 году как чистый алгоритм оптимизации, уменьшающий и уменьшающий области приемлемости (по аналогии с имитацией отжига , Киркпатрик, 1983). С 1970 года его использовали как для обычной оптимизации, так и для максимизации доходности.

эволюция и

Его также сравнивают с естественной эволюцией популяций живых организмов. В этом случае s ( x ) — это вероятность того, что особь, имеющая набор фенотипов x , выживет, дав потомство следующему поколению; определение индивидуальной приспособленности, данное Hartl 1981. Выход P заменяется средней приспособленностью, определяемой как среднее значение по множеству особей в большой популяции.

Фенотипы часто распределены по Гауссу в большой популяции, и необходимым условием для того, чтобы естественная эволюция могла выполнить теорему гауссовой адаптации в отношении всех гауссовских количественных признаков, является то, что она может сместить центр тяжести гауссова к центр тяжести выбранных особей. Этого можно добиться с помощью закона Харди-Вайнберга . Это возможно, поскольку теорема гауссовой адаптации справедлива для любой области приемлемости, независимой от структуры (Kjellström, 1996).

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

Как подняться на гору

Средняя приспособленность может быть рассчитана при условии, что известно распределение параметров и структура ландшафта. Реальный ландшафт неизвестен, но на рисунке ниже показан вымышленный профиль (синий) ландшафта вдоль линии (x) в комнате, охватываемой такими параметрами. Красная кривая представляет собой среднее значение, основанное на красной колоколообразной кривой внизу рисунка. Его получают, позволяя колоколообразной кривой скользить вдоль оси X и вычислять среднее значение в каждом месте. Как видно, небольшие выступы и ямки сглажены. Таким образом, если эволюция начинается в точке А с относительно небольшой дисперсией (красная колоколообразная кривая), то восхождение будет происходить по красной кривой. Процесс может застрять на миллионы лет в точках B или C, пока остаются впадины справа от этих точек, а скорость мутаций слишком мала.

Если частота мутаций достаточно высока, беспорядок или дисперсия могут увеличиться, и параметр(ы) может стать распределенным по типу зеленой колоколообразной кривой. Тогда восхождение будет происходить по зеленой кривой, которая еще более сглажена. Поскольку впадины справа от B и C теперь исчезли, процесс может продолжаться до пиков в D. Но, конечно, ландшафт накладывает ограничения на беспорядок или изменчивость. Кроме того, в зависимости от ландшафта процесс может стать очень скачкообразным, и если соотношение времени пребывания процесса на локальном пике и времени перехода к следующему пику очень велико, то это может выглядеть как прерывистый пик. равновесие , как предложил Гулд (см. Ридли).

моделирование

До сих пор теория рассматривала только средние значения непрерывных распределений, соответствующих бесконечному числу индивидов. Однако в действительности количество особей всегда ограничено, что приводит к неопределенности в оценке m и M (матрица моментов гауссианы). А это тоже может повлиять на эффективность процесса. К сожалению, об этом известно очень мало, по крайней мере теоретически.

Реализация обычной адаптации на компьютере – достаточно простая задача. Адаптация m может выполняться по одному образцу (индивидуальному) за раз, например

м ( я + 1) знак равно (1 – а ) м ( я ) + топор

где x — проходная выборка, а a < 1 — подходящая константа, так что обратная величина a представляет количество особей в популяции.

В принципе, M можно обновлять после каждого шага y, ведущего к допустимой точке.

x = m + y согласно:

M ( я + 1) = (1 – 2 б ) M ( я ) + 2 byy ^Т ,

где ты ^Т — транспонирование y , а b << 1 — еще одна подходящая константа. Чтобы гарантировать подходящее увеличение средней информации , y должен быть нормально распределен с матрицей моментов μ. ² M , где скаляр μ > 1 используется для увеличения средней информации ( энтропии информации , беспорядка, разнообразия) с подходящей скоростью. Но М никогда не будет использоваться в расчетах. Вместо этого мы используем матрицу W, определенную WW ^Т = М. ​

Таким образом, мы имеем y = Wg , где g нормально распределена с матрицей моментов µU , а U — единичная матрица. В и В ^Т может быть обновлено по формулам

W = (1 – b ) W + byg ^Т и Вт ^Т = (1 – б ) Вт ^Т + + ^Т

потому что умножение дает

M = (1 – 2 b ) M + 2 byy ^Т ,

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

W ( я + 1) = (1 – б ) W ( я ) + byg ^Т .

Это формула, используемая в простой двумерной модели мозга, удовлетворяющей правилу Хебба ассоциативного обучения; см. следующий раздел (Кьеллстрем, 1996 и 1999).

На рисунке ниже показан эффект увеличения средней информации в гауссовском PDF-файле, используемом для восхождения на горный гребень (две линии обозначают контурную линию). И красный, и зеленый кластеры имеют одинаковую среднюю приспособленность, около 65%, но зеленый кластер имеет гораздо более высокую среднюю информацию, что делает зеленый процесс намного более эффективным. Эффект этой адаптации не очень заметен в двумерном случае, но в многомерном случае эффективность процесса поиска может быть увеличена на многие порядки.

Эволюция мозга

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

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

• Ядро нервной клетки может добавлять значения сигналов,
• синапс может размножаться с постоянной и
• Аксон может задерживать значения.

Это основа теории цифровых фильтров и нейронных сетей, состоящих из компонентов, которые могут складывать, умножать и задерживать значения сигналов, а также многих моделей мозга, Левин, 1991.

На рисунке ниже предполагается, что ствол мозга передает паттерны распределенных по Гауссу сигналов. Это может быть возможно, поскольку некоторые нейроны активируются случайным образом (Кандел и др.). Стебель также представляет собой неупорядоченную структуру, окруженную более упорядоченными оболочками (Bergström, 1969), и согласно центральной предельной теореме сумма сигналов от многих нейронов может быть распределена по Гауссу. Треугольные прямоугольники представляют собой синапсы, а прямоугольники со знаком + — ядра клеток.

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

m и W обновляются в соответствии с:

м ₁ = 0,9 м ₁ + 0,1 х 1; м ₂ = 0,9 м ₂ + 0,1 х ₂ ;

ш ₁₁ = 0,9 ш ₁₁ + 0,1 у ₁ г ₁ ; ш ₁₂ = 0,9 ш ₁₂ + 0,1 у ₁ г ₂ ;

ш ₂₁ = 0,9 ш ₂₁ + 0,1 у ₂ г ₁ ; ш ₂₂ = 0,9 ш ₂₂ + 0,1 у ₂ г ₂ ;

Как можно видеть, это очень похоже на маленький мозг, управляемый теорией обучения Хебба (Kjellström, 1996, 1999 и 2002).

Гауссова адаптация

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

Такой случайный процесс дает нам большую свободу выбора, но вряд ли кто-то ее даст. Однако иллюзия воли может возникнуть из-за способности процесса максимизировать среднюю приспособленность, что приводит к поиску цели. То есть он предпочитает более высокие вершины ландшафта более низким или лучшие альтернативы худшим. Таким образом может появиться иллюзорная воля. Аналогичную точку зрения высказал Зохар 1990. См. также Кьеллстрем 1999.

Теорема

Эффективность гауссовской адаптации основана на теории информации Клода Э. Шеннона (см. Информационное содержание ). Когда событие происходит с вероятностью P , тогда может быть достигнута информация -log( P ). Например, если средняя приспособленность равна P , информация, полученная для каждого человека, выбранного для выживания, будет равна -log( P ) – в среднем – и работа/время, необходимые для получения информации, пропорциональны 1/ P . Таким образом, если эффективность E определяется как информация, деленная на работу/время, необходимое для ее получения, мы имеем:

Е = - P журнал( P ).

Эта функция достигает максимума при P = 1/ e = 0,37. Тот же результат был получен Гейнсом другим методом.

E = 0, если P = 0, для процесса с бесконечной частотой мутаций, и если P = 1, для процесса с частотой мутаций = 0 (при условии, что процесс жив).Эта мера эффективности справедлива для большого класса процессов случайного поиска при наличии определенных условий.

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

2 Все индивидуумы имеют равные затраты, а производная при P = 1 < 0.

Тогда можно доказать следующую теорему:

Все меры эффективности, удовлетворяющие указанным выше условиям, асимптотически пропорциональны – P log( P/q ) при увеличении числа измерений и максимизируются при помощи P = q exp(-1) (Kjellström, 1996 и 1999).

На рисунке выше показана возможная функция эффективности для процесса случайного поиска, такого как адаптация Гаусса. Слева процесс наиболее хаотичен, когда P = 0, тогда как справа наблюдается идеальный порядок, когда P = 1.

В примере Рехенберга, 1971, 1973, случайное блуждание проходит через коридор, максимизирующий параметр x ₁ . В этом случае область приемлемости определяется как ( n − 1)-мерный интервал параметров x ₂ , x ₃ , ..., x _n , но значение x ₁ ниже последнего принятого никогда не будет принято. Поскольку в этом случае P никогда не может превышать 0,5, максимальная скорость в направлении более высоких значений x ₁ достигается при P = 0,5/ e = 0,18, что согласуется с выводами Рехенберга.

Точка зрения, которая также может представлять интерес в этом контексте, заключается в том, что для доказательства теоремы не требуется никакого определения информации (кроме того, что точки выборки внутри некоторой области приемлемости дают информацию о расширении области). Затем, поскольку формулу можно интерпретировать как информацию, разделенную на работу, необходимую для получения информации, это также указывает на то, что -log( P ) является хорошим кандидатом на роль меры информации.

Алгоритм Штауффера и Гримсона

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

Но есть различия. В случае Штауффера-Гримсона информация не используется для управления генератором случайных чисел для центрирования, максимизации средней пригодности, средней информации или выхода продукции. Адаптация матрицы моментов также сильно отличается от описанной выше «эволюции мозга».

См. также

• Энтропия в термодинамике и теории информации
• Фундаментальная теорема Фишера о естественном отборе
• Свободная воля
• Генетический алгоритм
• Хеббианское обучение
• Информационный контент
• Имитация отжига
• Стохастическая оптимизация
• Стратегия эволюции адаптации ковариационной матрицы (CMA-ES)
• Единица выбора

Ссылки

• Бергстрем, Р.М. Энтропийная модель развивающегося мозга. Психобиология развития , 2 (3): 139–152, 1969.
• Брукс, Д.Р. и Уайли, Э.О. Эволюция как энтропия, На пути к единой теории биологии . Издательство Чикагского университета, 1986.
• Брукс, Д. Р. Эволюция в век информации: заново открывая природу организма. Семиозис, эволюция, энергия, развитие, том 1, номер 1, март 2001 г.
• Гейнс, Брайан Р. Управление знаниями в обществах интеллектуальных адаптивных агентов. Журнал интеллектуальных информационных систем 9, 277–298 (1997).
• Хартл, Д.Л. Учебник по популяционной генетике . Синауэр, Сандерленд, Массачусетс, 1981 год.
• Гамильтон, У.Д. 1963. Эволюция альтруистического поведения. Американский натуралист 97: 354–356.
• Кандел, Э.Р., Шварц, Дж.Х., Джессел, Т.М. Основы нейронауки и поведения . Прентис Холл Интернэшнл, Лондон, 1995 год.
• С. Киркпатрик, К. Д. Гелатт и М. П. Векки, Оптимизация путем моделирования отжига, Science, том 220, номер 4598, страницы 671–680, 1983.
• Кьеллстрем, Г. Оптимизация сети путем случайного изменения значений компонентов. Эрикссон Техникс , том. 25, нет. 3, стр. 133–151, 1969.
• Кьельстрем, Г. Оптимизация электрических сетей с учетом затрат на толерантность. Эрикссон Техникс , нет. 3, стр. 157–175, 1970.
• Кьеллстрем Г. и Таксен Л. Стохастическая оптимизация при проектировании систем. IEEE Транс. на Circ. и сист., вып. CAS-28, нет. 7 июля 1981 г.
• Кьельстрём Г., Таксен Л. и Линдберг П.О. Дискретная оптимизация цифровых фильтров с использованием гауссовой адаптации и минимизации квадратичной функции. IEEE Транс. на Circ. и сист., вып. CAS-34, № 10, октябрь 1987 г.
• Кьельстрем, Г. Об эффективности гауссовой адаптации. Журнал теории оптимизации и приложений , вып. 71, нет. 3 декабря 1991 г.
• Кьельстрем, Г. и Таксен, Л. Адаптация по Гауссу, эффективный глобальный оптимизатор, основанный на эволюции; Вычислительная и прикладная математика, В., К. Брезински и У. Кулиш (редакторы), Elsevier Science Publishers BV, стр. 267–276, 1992.
• Кьеллстрем, Г. Эволюция как алгоритм статистической оптимизации. Эволюционная теория 11:105–117 (январь 1996 г.).
• Кьеллстрем, Г. Эволюция мозга. Прикладная математика и вычисления , 98(2–3):293–300, февраль 1999 г.
• Кьеллстрем, Г. Эволюция в двух словах и некоторые последствия, касающиеся оценок. ЭВОЛЮЦИОНИРОВАТЬ, ISBN   91-972936-1-X , Стокгольм, 2002 г.
• Левин, Д.С. Введение в нейронное и когнитивное моделирование. Лоуренс Эрлбаум Ассошиэйтс, Инк., Издательство, 1991.
• Маклин, П.Д. Триединая концепция мозга и поведения . Торонто, Университет. Торонто Пресс, 1973.
• Мейнард Смит, Дж. 1964. Групповой отбор и родственный отбор, Nature 201: 1145–1147.
• Мейнард Смит, Дж. Эволюционная генетика . Издательство Оксфордского университета, 1998.
• Майр, Э. Что такое эволюция . Основные книги, Нью-Йорк, 2001.
• Мюллер, Кристиан Л. и Сбальцарини Иво Ф. Возвращение к гауссовской адаптации - энтропийный взгляд на адаптацию ковариационной матрицы. Институт теоретической информатики и Швейцарский институт биоинформатики , ETH Zurich , CH-8092 Цюрих, Швейцария.
• Пинель Дж. Ф. и Сингхал К. Центрирование и допуски статистического проектирования с использованием параметрической выборки. Транзакции IEEE в схемах и системах, Vol. Дас-28, №7, июль 1981 г.
• Рехнерберг, И. (1971): Эволюционная стратегия - оптимизация технических систем в соответствии с принципами биологической эволюции (докторская диссертация). Перепечатано Фромманом-Хольцбогом (1973).
• Ридли, М. Эволюция . Блэквелл Сайенс, 1996.
• Стауффер, К. и Гримсон, WEL, Изучение моделей деятельности с использованием отслеживания в реальном времени, IEEE Trans. о ПАМИ, 22(8), 2000.
• Штер, Г. Об исследовании пространства производительности аналоговых интегральных схем. Технический университет Мюнхена, диссертация, 2005 г.
• Таксен, Л. Структура координации развития сложных систем. Технологический институт Линчёпингского университета, Диссертация, 2003 г.
• Зохар, Д. Квантовое «я»: революционный взгляд на человеческую природу и сознание, основанный на новой физике . Лондон, Блумсбери, 1990.