ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

The article was published in issue no. № 4, 2008
Abstract:
Аннотация:
Author: () -
Keywords: search engine, neural network, Internet, search
Page views: 11070
Print version
Full issue in PDF (8.40Mb)

Font size:       Font:

Информационная среда www (World Wide Web), работающая на ресурсах сети Интернет, насчитывает огромное количество документов, которое вскоре может достигнуть 10 млрд. В настоящее время число новых документов, размещаемых на www, составляет более 1 млн в день. Кроме того, значительное количество уже существующих документов ежедневно изменяется (новости, бизнес, развлече- ния и т.д.). Постоянно увеличивающийся объем информации www (по некоторым оценкам по экспоненциальному закону) порождает проблему поиска релевантной информации по запросу пользователя.

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

Анализ работы поисковых машин Интернета показывает, что ни в одной из них нет индексов всех web-страниц: каждая поисковая система индексирует только часть этих страниц, причем разных. Объединить достоинства нескольких поисковых систем позволяют метапоисковые системы. Как правило, они не имеют собственных индексных баз данных, поэтому перенаправляют запросы пользователей другим поисковым системам, в том числе метапоисковым [3].

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

Перспективным подходом к организации систем поиска релевантной информации является использование новых информационных технологий на основе нейронных сетей (НС).

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

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

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

Широко используемыми методами локальной оптимизации являются методы Дэвидона–Флетчера–Пауэлла (Davidon, Fletcher, Pauel – DFP) и Бройдена–Флетчера–Гольдфарба–Шанно (Broyden, Fletcher, Goldfarb, Shanno – BFGS). Основное достоинство рассматриваемых методов – устойчивость получаемых результатов [1,2].

Экспериментальное исследование рассмотренных градиентных алгоритмов проводилось на достаточно представительном наборе тестовых функций (минимум которых известен), характеризующихся различной размерностью, количеством экстремумов, а также сложностью ландшафта изменений значений функций. Сравнение эффективности исследуемых алгоритмов выполнялось по двум показателям: сходимости (соотношению количества схождений к глобальному и к локальным минимумам) и вычислительной сложности (количеству вычислений значений оптимизируемой функции). В качестве тестовых функций использовались функции Роджерса, Жилинскаса, Химмельблау, Розенброка [1].

Результаты экспериментов представлены в таблице 1.

Таблица 1

Экспериментальное исследование градиентных алгоритмов

Показатель

Метод

Тестовая функция

Роджер- са

Жилин- скаса

Химмель- блау

Розен- брока

Сходимость (%)

Коши

27,7

0,3

92,7

7

DFP

29,4

0,1

96,9

75,5

BFGS

27,5

0,5

86,4

36,6

Среднее количество вызовов функции

Коши

3908

203

563

4569

DFP

768

235

377

2400

BFGS

2813

216,

412

1107

Анализ полученных результатов позволяет сделать вывод, что наилучшим по совокупности показателей сходимости и вычислительной сложности является оптимизация на основе DFP. Определены параметры НС (НС-Д и НС-К): топология (персептрон: 13–20–8 слоев), полученная с использованием алгоритма динамического наращивания узлов [1]; алгоритм обучения – алгоритм обратного распространения на основе DFP; коэффициент обучаемости 0,35; логистическая функция – суммирование; активационная функция сигмоидная.

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

Приведем результаты экспериментов с НС, используемой в разработанной метапоисковой системе, способной перенаправлять поисковые запросы пользователей в известные поисковые системы (табл. 2). В экспериментах участвовали 8 независимых пользователей из различных областей бизнеса.

Таблица 2

Статистика работы пользователей

Показатель

Пользователь

A

B

C

D

E

F

G

H

Кол-во запросов

18

23

59

144

156

189

203

438

Мин. оценка

2

3

2

1

4

3

0

0

Сред. балл

4,9

6,1

6,8

7,2

3,2

8,1

6,4

6,2

Макс. оценка

10

10

8

9

10

10

10

10

Сред.кол-во термов в запросе

3,50

2,16

3,10

2,89

2,71

2,44

2,23

2,57

Сред. кол-во символов в запросе

22,5

18,2

41,1

25,1

28,2

30,1

36,3

35,5

Среднее время отклика

15,0

11,5

13

14,5

12,0

19,2

18

14

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

Таблица 3

Итоговое распределение рангов поисковых систем (%)

Поисковая система

Пользователь

A

B

C

D

E

F

G

H

Яндекс

13,7

15,1

18,3

20,8

22,3

36,1

34,4

42,3

Рамблер

9,2

11,4

20,5

4,2

3,2

7,5

3,2

5,6

Google

8,67

11,2

22,0

13,6

19,0

25,2

48,3

14,7

Mail.ru

15,2

5,3

8,1

2,2

3,2

11,0

1,2

2,5

Yahoo

1,0

21,1

1,1

4,1

15,2

0,2

2,5

14,1

Апорт

22,0

15,2

0,2

39,5

21,1

0,3

4,2

5,8

MSN

19,7

10,6

11,3

8,1

6,2

5,2

3,8

2,3

Altavista

10,5

10,1

18,5

7,5

9,8

14,5

2,4

12,7

                         

Отдельные системы (Яндекс и Google) были эффективны для большинства пользователей. А такие системы, как MSN, Yahoo, оценены как неудобные, возможно, это связано с их слабой ориентацией на русскоязычных пользователей Интернета.

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

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

Для реализации алгоритма настройки фильтра необходимо более строго подойти к решению проблемы обучения НС, поскольку величина ошибки распознавания в значительной степени определяет эффективность работы системы. Целесообразно исследовать алгоритмы обучения НС с использованием методов глобального поиска минимума ошибки обучения на основе генетических алгоритмов (ГА) [2]. Проведенные исследования показали, что ГА обладает способностью быстро локализовать зону существования экстремума, но не позволяет получить точное решение с высокой вероятностью. Поэтому целесообразно проводить оптимизацию в два этапа. На первом с помощью ГА находится точка, лежащая в окрестности глобального минимума, а на втором из этой точки производится оптимизация одним из градиентных методов для получения уточненных значений экстремума.

Экспериментальное исследование двухэтапного алгоритма оптимизации осуществлялось на тех же тестовых функциях, что и алгоритмы BFGS и DFP. Результаты представлены в таблице 4.

Анализ полученных результатов позволяет сделать вывод, что наилучшим по совокупности показателей сходимости и вычислительной сложности (количеству вычислений значений оптимизируемой функции) является оптимизация на основе ГА на первом этапе и методом DFP на втором. Этот метод был использован для обучения НС-Д в разработанной метапоисковой системе.

Таблица 4

Экспериментальное исследование двухэтапного алгоритма оптимизации

Показатель

Метод

Тестовая функция

Роджер- са

Жилин- скаса

Химмель- блау

Розен- брока

Сходимость (%)

Коши

100

0,2

99,3

17,1

DFP

100

0,4

100

99,5

BFGS

99,9

0,3

99,1

48,8

Среднее количество вызовов функции

Коши

6356

2773

3092

7727

DFP

2987

2791

2835

3628

BFGS

4647

2763

2968

3718

Параметры НС: топология – персептрон (20–15–8 нейронов в слоях); обучение – последовательный ГА; логистическая функция – суммирование; активационная функция сигмоидная. Параметры ГА: размер популяции – 4000; кросинговер многоточечный; скрещивание 10 %; мутация 10 %; функция фитнеса – среднеквадратичное отклонение вектора оценок пользователей для различных фильтров и вектора выходных значений персептрона.

Таблица 5

Итоговое распределение коэффициентов эффективности между типами фильтров

Тип фильтра

Пользователь

A

B

C

D

E

F

G

H

Слова подряд

11,22

12,36

14,68

18,46

21,49

28,62

15,80

35,89

Слова в одном предложении

12,45

11,12

11,20

15,27

16,32

21,14

24,16

6,90

Слова в одном документе

10,56

13,48

8,95

11,09

12,48

16,83

14,23

16,40

Слова в заданной последовательности

8,62

7,36

9,14

8,12

8,11

12,88

6,50

11,20

Любое выделенное слово

9,46

8,16

12,87

7,24

5,16

2,14

1,90

1,84

Без учета морфологии

7,43

7,11

10,24

2,56

0,23

4,18

0,97

3,50

В тексте

8,16

11,24

10,86

0,98

0,98

0,14

0,24

0,11

В заголовке

8,16

6,12

11,54

8,14

3,23

1,50

5,49

1,12

Только на русском языке

11,45

14,26

6,24

24,15

27,18

11,25

29,30

19,86

Не исключая стоп-слова

12,49

8,79

4,28

3,99

4,82

1,32

1,41

3,18

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

Распределение средних оценок документов

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

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

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

Список литературы

1.  Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. В 2 кн. – М.: Мир, 1986.

2.  Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 400 с.

3.  Осипов Г.С., Тихомиров И.А., Смирнов И.В. Интеллектуальный поиск в глобальных и локальных вычислительных сетях и базах данных. // Тр. Междунар. конф.: Программные системы: теория и приложения. – ИПС РАН, Переславль-Залесский. – 2004. – Т. 2. – С. 21–34.


Permanent link:
http://swsys.ru/index.php?page=article&id=1630&lang=&lang=&like=1&lang=en
Print version
Full issue in PDF (8.40Mb)
The article was published in issue no. № 4, 2008

Perhaps, you might be interested in the following articles of similar topics: