Классификация алгоритмов эвристического поиска

Различают алгоритмы:

1. Поиск в глубину - использует эвристическую функцию вида F(n) = ^h(n). Это жадный алгоритмы, которые выбирают на каждом шаге наилучшее решение для продолжения.

2. Поиск в ширину (переборный) - работают с эвристической функцией вида F(n) = g(n) и ориентируются на совершенные затраты

3. Смешанный поиск - работают с эвристической функцией вида F(n) = a* (n+ (1-a)*g(n). 0 <=a <= 1. Следует найти a. Считается что на ранних этапах следует брать a = 0, а на поздних полагают a = 1, т.е. переводят на жадный вариант поиска.

 

 

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

Нейронные сети представляют собой упрощённую модель человеческого мозга. Мозг состоит из нейронов, которые рассматриваются как индивидуальные процессоры.

Математическая модель поведения клетки мозга создали Макколок и Питс.

Коэффициенты ai задаются в процессе обучения, или путем решения системы уравнений. Если y > 0, то считается что нейрон распознал образец. На практике нейроны обычно объединяют в сеть.

Xi – соответствует ключевым словам (если xi = 1, то слово присутствует в запросе)

Для вычисления коэффициентов ai используют формулы sqrt((xi - xэ)²) -> min:

(x_i - x_э)² -> min

x_i² – 2x_i*x_э + x_э² - > min

2x_i*x_э – x_э² -> max

2x_э1*x₁ + 2x_э2*x2 + … + 2x_эn*x_n – x_э1² – x_э2² - … - x_эn² -> max

2x_эi === a_i

 

Для нейрона с линейной функцией распознавания процедура обучения такова:

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

Нейрон отклонил образец – a_i = a_i гамма * x_i

нейрон принял неправильный образец и не распознал его a_i = a_i гамма * x_i

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

Класс

Док-т

a

b

c

d

e

f

g

h

j

k

q

t

W1

D1

W1

D2

W1

D3

W1

D4

W2

D5

W2

D6

W2

D7

W2

D8

W2

D9

 

Переменные a – t задают ключевые слова. Пусть нейрон распознает класс W1, пусть эталонный документ класса x_э =< 111110000000

2a+2b+2c+2d+2e+0f + 0g+0h+0j+0k+0q+0t – 5.

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

Для документа D4 правило не сработало (значение распознающей функции < 0, хотя D4 принадлежит W1)

Корректируем

D4 <101000001000> = 3a+2b+3c +2d + 2e+ 1j – 5

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

Теорема Колмогорова-Габора:

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

Более точную аппроксимацию дает кривая вида

Полином второй степени от двух кривых в общем виде:

P(x₁, x₂) = C₁x₁² + C₂x₂² + C₃X₁X₂+ C₄x₁ + C₅X₂ (4)

Полином третьей степени

P(x₁, x₂) = C₁x₁³ + C₂x₂³ + C₂x₂³+ C₃X₁X₂+ C₄x₁ + C₅X₂ (4) …???

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

Рассмотрим пример:

Рассмотрим полином второй степени. Пусть обучающая выборка представлена таблицей

X1	X2	Класс
		A
		A
	0.5	A
0.5	0.5	B
0.2		B
		B

 

Допустим, что линейную функцию для этой таблице нельзя, тогда расширимэту таблицу членами второго порядка, получим таблицу:

X1	X2	X1^2	X2^2	X1X2	Класс
					A
					A
	0.5		0.25	0.5	A
0.5	0.5	0.25	0.25	0.25	B
0.2		0.04		0.8	B
					B

 

Теперь можно построить линейную функцию вида

y = a₁x₁ +a₂x₂+a₃+z₁ +a₄z₂+a₅+z₃,

z₁ = x₁²,

z₂ = x₂²,

z₃ = x₁x₂.

Теорема Колмогорова-Габора гарантирует, что при весьма общих условиях требуемый полином все построить удастся.