Неоднозначные грамматики. Ассоциативность

Рассмотрим конфигурации, возникающие при анализе строки 1+2+3.

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

Таким образом, существуют ряд стандартных ситуаций, в которых возникают неоднозначные грамматики. Большая часть подобных ситуаций может быть решена преобразованием грамматик («висящие» else, приоритет операций и т.д.), но не всегда это необходимо («висящие» else) и не всегда является лучшим решением. Существуют ситуации, когда подходящее преобразование грамматики не существует, в таких случаях необходимо привлекать дополнительные механизмы, как это сделано, например, для определения ассоциативности операций.

11, 12, 13, 14.

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

Классификация ИНС.

1. ИНС без обратных связей
1. однослойный персептрон
2. многослойный персептрон
2. ИНС с обратными связями
1. сети Хопфилда
2. сети ассоциативной двунаправленной памяти (ДАП)
3. сети (карты) Кохонена
4. сети адаптивной резонансной теории (АРТ)

1. Однослойный персептрон

1. Многослойный персептрон

Фиксируется ввод и вывод, меняются параметры. Обучение (настройка) – изменение весовых коэффициентов.

1. Сети Хомфилда

Если подать фрагмент и он однозначен, то сеть должна восстановить целое.

1. Сети ассоциативной двунаправленной памяти (ДАП)

Создаёт ассоциации: А_i ® B_i

1. Cети (карты) Кохонена

Обучение по принципу «победитель – забирает всё».

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

1. Сети адаптивной резонансной теории (АРТ)

Слой А – слой сравнения

Слой B – слой распознавания

Обладает свойством классичности, т.е. дообучаемости

Методы обучения

Алгоритмы обучения бывают с учителем и без. Алгоритм называется алгоритмом с учителем, если при обучении известны и входные, и выходные вектора сети. Имеются пары вход + выход — известные условия задачи и решение. В процессе обучения сеть меняет свои параметры и учится давать нужное отображение X ®Y. Сеть учится давать результаты, которые нам уже известны. За счет способности к обобщению сетью могут быть получены новые результаты, если подать на вход вектор, который не встречался при обучении.

Алгоритм относится к обучению без учителя, если известны только входные вектора, и на их основе сеть учится давать наилучшие значения выходов. Что понимается под “наилучшими” — определяется алгоритмом обучения.

Перцептрон обучается с учителем. Это означает, что должно быть задано множество пар векторов {x^s,d^s}, s =1...S, где {x^s}={x¹,..., x^S } — формализованное условие задачи, а {d^s}={d¹,..., d^S } — известное решение для этого условия. Совокупность пар {x^s,d^s} составляет обучающее множество.

S — количество элементов в обучающем множестве — должно быть достаточным для обучения сети, чтобы под управлением алгоритма сформировать набор параметров сети, дающий нужное отображение X →Y.

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

Выберем один из векторов x^s и подадим его на вход сети. На выходе получится некоторый вектор y^s. Тогда ошибкой сети можно считать для каждой пары (x^s,d^s). Чаще всего для оценки качества обучения выбирают суммарную квадратическую ошибку: . Реже применяется средняя относительная ошибка: . Ее преимущество в том, что она дает значение, не зависящее напрямую ни от количества примеров в обучающем множестве, ни от размерности выходного вектора, и имеет удобное для восприятия человеком значение в интервале от 0 до 100%.

Задача обучения перцептрона ставится так: подобрать такие значения параметров сети, чтобы ошибка была минимальна для данного обучающего множества {x^s,d^s }.

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