Обработка знаний в нейронных сетях

Лекция 3

Методы поиска решений комбинаторных задач

 

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

Такие алгоритмы называют эвристиками. Имеется не­сколько причин, благоприятствующих распространению этих алгоритмов:

1. Когда не существует точного метода решения задачи или когда для этого требуется много вычислительного времени или памяти машины.

2. Когда нет необходимости получения оптимального решения.

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

Напротив, один из недостатков эвристик заключается в том, что в общем случае невозможно узнать, как близко от оптимального х* найденное решение хлучшее. Если решается за­дача максимизации, то нам известно, что хлучшееЈx*. Без сомне­ния, существует метод для реализации взвешиваний (размежевания), состоящий в уменьшении задачи (удаляя, на­пример, некоторые из ограничений или осуществляя “релаксацию Лагранжа” таким образом, чтобы ее легко было решить). Если оптимум уменьшенной задачи есть х’ и извест­но, что xлучшееЈx*Јx’, то значение х’ приближается к хлучшее и гарантирует, что эвристика дает хорошую аппроксимацию. Существуют различные типы эвристик, соответствующие спо­собам достижения решения.

Конструктивные методы. Эти методы позволяют постепенное приближение к решению путем добавления к нему отдельных компонент до того момента, пока не получится выполнимое решение. Наиболее распространенный из этих алгоритмов – алгоритм ‘’greedy”, который строит шаг за шагом решения, отыскивая максимум выгоды на каждом шаге. Рассмотрим задачу о рюкзаке. Это задача о рациональной загрузке рюкзака, который имеет ограничение по объему. Каждый помещенный в рюкзак предмет имеет определенную значимость. Задача состоит в определении загрузки рюкзака такими предметами, которые приносят наибольшую суммарную пользу. Для решения этой задачи в соответствии с гриди (“greedy”) алгоритмом осуществляется движение между еще не отобранными элементами, и выбираются те из них, которые несут наибольшее значение на единицу объема, повторяя про­цесс до тех пор, пока не достигается больше продуктов.

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

Манипулирование с моделью. Эти эвристики изменя­ют структуру модели с целью сделать ее более простой и получения ее решения в качестве результата исход­ной задачи. Она может состоять в уменьшении пространст­ва решений (сделать линейные функции вместо нелинейных; сгруппировать переменные с целью уменьшения их количест­ва; наложить новые ограничения на поведение, ожидая полу­чить оптимальное решение и т.д.) или увеличении этого про­странства (исключить ограничения в задаче).

Методы локального улучшения. Эти методы касают­ся получения выполненного решения на основе одного из ре­шений (возможно полученных другими эвристиками) и по­средством альтернативы его, базируясь на других выполненных решениях, но лучшей стоимости. В эту послед­нюю группу входят эвристики, которые позволяют реализо­вать переход от одного выполненного решения к другому. В связи с этим определяют окрестность N(s) решения s, т.е. мно­жество решений подобных s. Слово “подобных” здесь понима­ется в том смысле, что можно получить одно s’ОN(s) исходя из решения s с помощью одной элементарной операции над s (удалить или добавить элемент, поменять элементы местами и т.д.).

Пусть в задаче о рюкзаке из пяти элементов имеем следующее ре­шение: s={1,0,0,1,1}, где xi=1 означает, что выбран элемент i. Можно рассматривать в качестве окрестности s все те реше­ния, в которых заменяется один из выбранных элементов дру­гим. Таким образом, в N(s) могло бы входить решение s’={0,0,1,1,1}, где удаляется первая единица и помещается третья.

Эти методы называются также эвристическими стра­тегиями. Они не предполагают наличия процедуры и основы­ваются на поиске решения среди элементов окрест­ности N(s), имеющего лучшее значение, которое улучшается до тех пор, пока не получается луч­шее решение.

Одно из главных неудобств этих методов состоит в существовании локальных оптимумов, если имеется s’ОN(s), c(s), c(s’) (предполагается, что целью является минимизация и что c(s) представляет стоимость ре­шения s (рис. 1.4)). Если в процессе поиска мы попали вначале в локальный оптимум, то эвристика будет продолжать поиск оптимального решения, а затем покинет эту ложную точку.

 

Рис. 1.4. Пример функции с локаль­ным оптимумом: N(xi)={xi-1,xi+1}

Другая проблема эвристических стратегий состоит в создании независимых начальных решений. Очевидно, что начальная точка имеет большее влияние на возможность поки­нуть или нет локальный оптимум. Например, на рис. 1.4, если отправиться от точки xi-2, то можно избежать риска.

Эвристический поиск. Алгоритм А*. В интеллектуальных информационных системах (ИИС) знания обычно накапливаются фрагментарно и нельзя зара­нее определить цепочку логических выводов, в которых они используются. Поэтому методом проб и ошибок выбирается некоторая цепочка выводов, ведущая к цели, и в случае неус­пеха осуществляется перебор с возвратами для поиска других цепочек выводов. Такой метод позволяет найти выход в самых различных ситуациях и свидетельствует о гибкости ИИС. Предложенный метод состоит из следующих шагов:

1. Выбрать некоторое действие из множества возмож­ных действий.

2. Выполнить выбранное действие, тем самым изменив текущую ситуацию.

3. Оценить ситуацию.

4. Отбросить бесполезные ситуации.

5. Если достигнута цель (конечная ситуация), то конец, иначе выбрать новую исходную ситуацию и начать сначала.

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

Рассмотрим более детально алгоритм А*. Всякой ситуа­ции S, полученной из исходной ситуации в результате выпол­нения некоторой цепочки действий, придается численная оценка

f(S) = g(S)+h(S),

где g(S) – реальная текущая стоимость ситуации S, h(S) – эври­стическая функция, которая оценивает стоимость наилучшей последовательности действий, ведущей от состояния S к цели (решению). Следовательно, f (S) – мера стоимости ре­шений, “подчиненных” ситуации S, т.е. решений, включающих то же подмножество исходных действий, что и S. Пусть с(S1,S2,a) – стоимость перехода из S1 в S2 с помощью действия a. Тогда g(S) равна сумме стоимостей действий, которые нужно выполнить, чтобы перейти от исходной к текущей ситуации.

Описание этого алгоритма удобно рассмотреть на при­мере игры в восемь (инвариант игры в пятнадцать). На поле 3х3 размещены восемь пронумерованных шашек. Цель игры: от заданного начального состояния перейти к целевому:

 

(За одно действие в пустую клетку можно поставить фишку, расположенную по соседству по вертикали или горизонтали.)

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

С помощью указанных операторов и оценочной функ­ции будем осуществлять поиск оптимального решения в про­странстве состояний. Пусть f(n) – стоимость оптимального пу­ти к цели от первой вершины (начального состояния) через n вершин дерева поиска:

f(n)=g(n)+h(n),

где g(n) – стоимость оптимального пути от первой до n-й вер­шины, h(n) – стоимость оптимального пути от n-й вершины до цели.

Будем считать, что стоимость перемещения одной фиш­ки равна 1 (единица), т.е. оптимальным считается решение с минимальным числом ходов.

В процессе поиска в общем случае нельзя знать f(n), по­этому рассмотрим априорное значение f’(n). В момент прохо­ждения n-й вершины g(n) известно и поэтому можно написать: f’(n)=g(n)+h’(n). Если представить пространство состояний в виде дерева, то g(n) – это глубина от первой до n-й вершины. В качестве h’(n), например, выберем число фишек, расположен­ных не на своих местах.

На рис. 1.5 показан результат поиска. Справа от каж­дой ситуации приводится пара значений g(n) и h(n).

 

десь важно, что h’(n)Јh(n), а истинно, если априорное значение стоимости от n-й вершины до цели меньше или равно истинной стоимости оптимального пути к цели, то это гаран­тирует, что обязательно будет найден оптимальный путь. По­скольку h’(n) – число фишек, находящихся не на своих местах, и h’(n) Јh(n), то мы не достигнем цели, пока число перемеще­ний меньше числа фишек, находящихся не на своих местах. Если выбрать h’(n)=0, то мы имеем горизонтальный поиск, при котором раскрываются близлежащие вершины (число таких вершин быстро возрастает), и оптимальный путь при этом в конце концов на­ходится. Если h’1(n)< h’2(n)Ј h(n), то можно дока­зать, что число вершин, раскрытых при поиске с использова­нием функции f1(n)=g(n)+h’1(n) меньше, чем при использова­нии функции f’2(n)=g(n)+h’2(n). А именно, h(n) можно рассмат­ривать как объем эвристических знаний, предсказывающих стоимость пути от цели до цели. Следовательно, поиск тем оптимальнее, чем больше имеется эвристических знаний: h2(n)>h1(n).

Было предложено несколько вариантов этого алгоритма. В качестве f(S) использовалась f (S)=(1-a)g(S)+ ah(S), где a – константа, aО[0,1].

Таким образом, указывается определенный баланс меж­ду известной g(S) и эвристической составляющей h(S). Алго­ритму А* соответствует a=1/2. При a=1 имеем градиентный метод, а при a = 0 – метод полного перебора.

 

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

 

Нейронные сети

 

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

 

Нейроны и связи между ними

 

Основные компоненты искусственных нейронных сетей моделируют структуру мозга. Мозг состоит из нейронов, кото­рые являются малыми единицами обработки информации. Нейроны получают вход либо из внешнего окружения, либо от других нейронов. Нейроны соединены в большую и сложную сеть. Сеть состоит из дендритов, ко­торые передают сообщения через различные пути в сети. Дендриты можно себе представить как дороги или скоростные пути, связывающие различные города (нейроны).

Связь этой сети с некоторым нейроном называется си­напсом или синоптической связью. Синапс можно рассматривать как точку соединения, в которой принимаются сигналы дендритами. Нейроны имеют много таких точек соединения в сети. Нейрон может иметь до 10000 синапсов. Уникаль­ной способностью нейрона является прием, обработка и пере­дача электрохимических сигналов по нервным путям. Принятые синапсом входные сигналы суммируются, причем одни входы стремятся возбудить нейрон, другие – вос­препятствовать его возбуждению. Когда суммарное возбужде­ние в теле нейрона превышает некоторый порог, нейрон воз­буждается, посылая сигнал другим нейронам.

Искусственный нейрон имитирует в первом приближе­нии свойства биологического нейрона. В нейрон поступает некоторое множество входных сигналов из внешней среды или из других нейронов. Множество этих входных сигналов, обозначаемое вектором х1,...xn, соответствует сигналам, приходящим в синапсы биологическо­го нейрона. Каждый входной сигнал xi умножается на соответствующий вес wi и поступает на суммирующий блок. Вес wi соответствует “силе” одной биологической синаптической связи. Множество весов обо­значается вектором W. Сумми­рующий блок, соответствующий телу биологического элемента, складывает взвешенные входы и создает выход, который будем обозначать NET (рис. 1.6). С использованием векторных обозначений NET=XW.

 

Рис. 1.6. Искусственный нейрон

Нейроны соединяются в сеть путями, в которых выход одного нейрона служит в качестве входа другого нейрона. Эти пути, как правило, являются однонаправленными. Однако не запрещается использовать двунаправленную связь между дву­мя нейронами (рис. 1.7).

 

 

Рис. 1.7. Двунаправленная связь нейронов

 

Одним из наиболее важных элементов при проектиро­вании нейронных сетей является “сила” связи между двумя нейронами, обозначаемая весом этой связи wij. При двунаправ­ленной связи между нейронами i и j, как

правило, wij№wji. Область знаний формируется и хранится как множество значений этих весов и система обучается новым знаниям путем установления весов связей.

Рассмотрим более подробно входы и выходы нейронов. Нейрон i получает импульсы от n других нейронов, с которы­ми он соединен в сети. Поскольку нейрон i получает много входных импульсов, то его чистый вход равен:

NETi = S wji OUTj

где j – все нейроны, соединенные с нейроном i.

В некоторых сетях абсолютное значение весов ограничены интервалом от 0 до 1. Эта нормализация позволяет избежать больших значений на входе нейрона.

 

Обработка знаний в нейронных сетях

 

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

Данные, вводимые во входной слой, отображают факты о проблеме принятия решения, например о примене­нии закладной на кредит. После ввода данных в сеть нейроны входного слоя возбуждаются и создают выход на другие слои системы. Обработка знаний в нейронной сети состоит из взаи­модействия между слоями нейронов в системе. Эта обработка продолжается до удовлетворения некоторого условия, после чего нейроны выходного слоя возбуждаются и передают их выход во внешнюю среду.

Таким образом, проектирование связей между нейрона­ми эквивалентно программированию системы для обработки входа и создания желаемого выхода. Проектирование нейрон­ной сети состоит из:

· упорядочивания нейронов по слоям;

· определения связей между нейронами различных слоев, так же, как и между нейронами внутри слоя;

· решения о том, каким образом нейрон получает вход и как создает выход;

· определения силы связей внутри сети, чтобы узнать соответствующие значения весов путем использова­ния контрольного набора данных.

В нейронной сети обычно имеется много связей между нейронами. Они группируются по слоям и в каждом слое располагаются нейро­ны одного типа. Нейроны в слое могут иметь или не иметь связи между собой – так ведут себя во многих простых проектах ней­роны одного слоя.

Нейронная сеть может иметь один (однослойная) или много (многослойная) слоев. При иерархической связи нейро­ны нижнего слоя связаны только с нейронами следующего уровня. Если связь не иерархического типа, то нейроны одного слоя могут посылать свои выходы не только нейронам сле­дующего слоя, но и другим слоям.

Простейшая нейронная сеть состоит из одного слоя нейронов и показана на рис. 1.8. Вершины-круги слева служат лишь для распределения входных сигналов, не выполняют каких-либо вычислений и поэтому не считаются слоем. Элементы из множества входов Х отдельными весами соединены с искусственными нейронами.

Рис. 1.8. Однослойная искусственная нейронная сеть

 

Искусственные ней­ронные сети с многочисленными слоями нейронов обладают большими возможностями и позволяют наиболее полно моде­лировать работу мозга. В последние годы были разработаны алгоритмы для их обучения. Выход одного слоя является вхо­дом другого (рис 1.9).

 

 

Рис. 1.9. Двухслойная искусственная нейронная сеть

 

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

Y=(XW1)ЧW2=X(W1W2)

 

Персептрон – это первая нейронная сеть, разработанная Ф. Розенблатом в 1957 году с целью моделирования психоло­гических аспектов мозга. Модель показала, что сеть может моделировать средства ассоциативной памяти мозга с их пря­мыми связями между слоями нейронов, которые способны обучаться, когда внешний вход имеет шумы и неточно­сти

На идеях персептрона был разработан компьютер, кото­рый распознавал изображения, в виде символов.

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

 

Нейроны второго слоя отмечают свойства некоторого примера или изображения. Третий слой является выходным и каждый нейрон в нем выдает или не выдает сиг­нал. Этот слой имеет обратную связь со вторым слоем. В на­чале работы персептрон не имеет полной связи между вторым и третьим слоями. Она будет создаваться в процессе обучения персептрона.

Обучение персептрона

 

Процесс обучения заключается в формировании весов связей между вторым и третьим слоями в соответствии со следующим уравнением:

 

где wji – весовая связь нейрона j второго слоя с нейроном i третьего слоя, DESOUT, – “желаемый” или правильный выход нейрона i третьего слоя и OUTi – реальный выход нейрона i.

Уравнение обучения персептрона имеет простое объяс­нение. Если нейрон i посылает правильный импульс (выход) во внешнюю среду, то веса к нейронам второго слоя не из­меняются. Однако, если выход нейрона i равен единице, когда он должен быть равен нулю, то весовые связи с нейронами второго слоя уменьшаются путем умножения на величину a. Если, с другой стороны, нейрон i имеет выход 0, когда пра­вильный импульс равен 1, то весовые связи к нейронам второ­го слоя увеличиваются путем умножения на величину a, где 0 Ј a Ј 1. Значение должно быть положительным, меньшим или равным единице.

Обучение персептрона происходит следующим образом. На вход персептрона подают по одному множество образов и подстраивают веса до тех пор, пока не будет достигнут тре­буемый выход. Допустим, что образ (символ) изображен на странице в клетку и от каждой клетки на персептрон подается вход. Если в клетке имеется линия (часть изображения), то от нее подается 1, в противном случае – 0. Таким образом, множество клеток за­даёт, таким образом, множество нулей и единиц, которое по­дается на вход персептрона. Цель состоит в том, чтобы нау­чить персептрон включать индикатор при подаче на него мно­жества входов, задающих нечетное число, и не включать в случае четного.

Обучение персептрона состоит в том, что на его вход подается образ Х и вычисляется выход Y. Если Y является пра­вильным, то веса не меняются. Однако, если выход неправи­лен, то веса изменяются так, чтобы уменьшить ошибочный результат.

За конечное число шагов сеть научится разделять стра­ницы с изображениями, соответствующими четным и нечет­ным числам. Это значит, что для всех страниц с нечетными числами выход будет больше порога, а для всех страниц с четными – меньше.

 

 

---

Дата добавления: 2019-07-15; просмотров: 312; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!