Алгоритм решения системы линейных алгебраических неравенств

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

X1 X2 Y
>=0
-1 >=0
>=0
>=0
<0
<0
<0
<0

По данной таблице запишем следующую систему неравенств:

2a1 + 4a2 >=0

-1a1 + 3a2 >=0

0a1+1a2 >=0

2a1+5a2>=0

3a1+2a2<0 (5)

6a1+3a2<0

a1+a2<0

4a1+3a2<0

Имеется проблема. Необходимо избавиться от строгих неравенств (> или 0, такую что c1a1+c2a2 <0 можно заменить на c1a1+c2a2 <= -E. Такая подстановка может привести к тому, что система не будет иметь решение.

Зададим E = 1 и приведем все неравенства к нестрогому виду

2a1 + 4a2 >=0

-1a1 + 3a2 >=0

0a1+1a2 >=0

2a1+5a2>=0 (6)

-3a1-2a >=1

-6a1-3a2>=1

-a1-a2>=1

-4a1-3a2>=1

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

1. На первой фазе нужно получить систему базисных неравенств вида ai >=0

2. Вторая выполняется как и первая, но уже при наличии базисных неравенств

Если на второй фазе в процессе итераций встречается невязка, причем, все коэффициенты в левой части не положительны, то устанавливаем факт неразрешимости системы неравенств.

Пример:

Возьмем невязку -3a1-2a >=1 и выведем из нее переменную a1:

a1 <= -1/3 – 2/3a2

a1 = -1/3 – 2/3a2 - z1, z1 – новая не отрицательная переменная (7)

подставим (7) в (6)

8/3a2 – 2z1= 2/3

11/3a2+z1>=-1/3

a2>=0

11/3a2-2z1>=2/3 (8)

z1>=a2

a2+6z1>=-1

-1/3a2+z1>=2/3

-1/3a2+4z1>=-1/3

Первая фаза завершена и имется два базисных неравенства a2>=0 и z1>=0

Вторая фаза выполняется с небольшим отличием от первой: из невязки выражаем переменную с положительным коэффициентом, например, 8/3a2 – 2z1= 2/3:

Из 8/3a2 – 2z1= 2/3 выражаем a2

a2>=1/4+3/4z1

a2=1/4+3/4z1+z2 (9)

15/4z1+11/3z2 >= -5/4

3/4z1+z2 >= -1/4

3/4z1+11/3z2 >= -1/4

Z1>=0 (10)

27/4z1+z2 >= -5/4

3/4z1-1/3z2 >= 3/4

15/4z1-1/3z2 >= -1/4

z1 = 1+4/9z2+z3 (11)

Подстановка 11 приводит к системе невязок. В этой системе решение дает z2=z3 = 0; отсюда в силу подстановок 7, 9, 11 найдем a1=-2, a2=1.

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

Обучение нейронных сетей

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

S = ∑(ai*xi),

ai – входные сигналы из нижестоящих слоев на вход верхним.

Процесс обучения состоит в следующем:

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

b’j = y’j*(dj-oj) (2)

(dj-oj) – Разность между ожидаемым и фактическим сигналом на выходе нейрона

y'j – значение производной выходного сигнала j-го элемента выходного слоя

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

S – вычисляемая сумма, y – значение выходного сигнала получаемого по формуле:

y = 1/(1-e-s) (3)

S= 0 y=0.5; S->+∞

dU(x)/dV(x) = (U’v – V’U )/ V2

y’= dy/dS = e-s/(1+e-s)2 =y(1-1/*1+e-s)) = y(1-y) (4)

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

Wzj = n*bj*yz bj – сигнал ошибки j-го выходного нейрона, yz – выходной сигнал от предыдущего нейрона z, поступающий на вход нейрона j, n – коэффициент регулирующий скорость обучения (обычно = 1)

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

bz = y’z ∑bjWzj (7)

Веса вычисляются по формуле 5.

Описанный алгоритм получил название «Обучение на основе обратного распространения ошибки».

Пример

На вход подаем 0 и 1, нейрон 5 выходной, 3,4 – скрытый слой. Выходная функция нейрона 3:

S3=w0,3(1) + w1,3*0 + w2,3*1 = 1*1+1*0+0.5*1 =1.5.

От этого значения вычисляется сигмоидальная функция:

U3 = y(1.5) ~= 0,817 из формулы 3.


S4 = w0,4*1+w2,4*1+w1,4*0 = 1*1+ (-1 * 0) + 2 * 1 = 3

U4 = y (3) ~= 0.952 из формулы 3

S5 = w0,5*1 + w3,5 * U3 + w4,5 * U4 = 1*1 +1.5*0.817+ (-1*0.952) = 1,27

U5 = y(1,27)~= 0.781 из формулы 3

Правильный сигнал на выходе пятого нейрона должен быть равен 1. Т.к. мы получили значение < 1 производим коррекцию. Вычисляем сигнал ошибки по формуле:

5= y’5(d5-o5) = y5 (1-y5) * (d5-o5) = 0.781* (1-0.781) * (1-0.781) = 0.037

Далее находим сигнал ошибок от нейронов 3 и 4 по формуле 7.

3= y’3 * ∑ 5*w3,5 = u3*(1-U3) * 5*1,5 = 0,0083

4= y’4∑ 5*w4,5 = U4(1-U4) * 5* (-1) = 0,952 * (1-0,952) *0,037* (-1) = -0,0017

Далее пересчитываются веса связей (Wzj). Примем £ = 0.5

W3,5 = w3,5 + £* 5+U3 = 1,5 + 0.5*0.037 * 0.817 = 01.525

W4,5 = w4,5 + £* 5* U4 = -0.982

W0,5= w0,5+£*Смещени5 = 1,052

Далее производим коррекцию весов w1,3 w2,3 w1,4 w2,4. Для примера рассмотрим только коррекцию веса w2,3:

W2,3 = W2,3+£* *U2 = 0.5 + 0.5*0.0083 *1 = 0.504

И так далее по аналогии…

Семантическая обработка текста. Проблема поиска по ключевым словам

При работе с текстом как с базой знаний мы имеем дело с текстом как с семантическим объектом. С такой базой знаний следует организовать интерфейс. Интерфейс предполагает обработку вопросов, организацию контекстной помощи, тестирования знаний и т.д. Семантический вопрос требует выдачи точного или точечного ответа.

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

referatqsx.nugaspb.ru refanrf.ostref.ru refalcu.ostref.ru refanlw.ostref.ru Главная Страница