Содержание к диссертации
Введение
1 Актуальность разработки эффективных процедур ранжирования в информационно-поисковых системах 13
1.1 Анализ проблем интеллектуального поиска текстовой информации 13
1.1.1 Особенности информационно-поисковых систем и методов поиска информации 13
1.1.2 Место и роль ранжирования в процедурах поиска 16
1.2 Обзор методов решения дискретных задач оптимизации информационно-поисковых процедур 18
1.2.1 Цели и задачи дискретных оптимизационных задач и их вычислительная сложность 18
1.2.2 Точные методы 31
1.2.3 Эвристические алгоритмы 36
1.3 Анализ нейросетевых моделей оптимизации информационно-поисковых процедур 38
1.3.1 Обзор технологии в применении к оптимизационным задачам 38
1.3.2 Показатели эффективности решения оптимизационных задач на основе нейросетей 47
1.4 Выводы 53
2 Разработка метода ранжирования в ИПС на основе динамической нейронной сети с бинарной функцией выхода 55
2.1 Метод ранжирования документов в ИПС на основе нейросетевого решения комбинаторных задач 56
2.1.1. Общая последовательность метода 56
2.1.2. Представление метода ранжирования нейросетевым решением комбинаторной задачи о назначениях и сортировки 59
2.2 Нейросетевая модель ранжирования документов на основе динамической сети Хопфилда с бинарной функцией выхода 66
2.2.1 Синтез архитектуры и параметров нейронной сети Хопфилда с бинарной функцией выхода 66
2.2.2 Использование модели через релаксацию энергетической функции сети Хопфилда 78
2.3 Особенности алгоритма ранжирования на основе синтезированной модели 83
2.3.1 Детерминированный подход в использовании синтезированной модели 83
2.3.2 Алгоритм идентификации отключаемых нейронов при последовательном прохождении дерева решений задачи ранжирования 86
2.4 Алгоритм нейросетевого ранжирования 88
2.5 Выводы 91
3 Архитектура, алгоритмы и программная реализация процедур ранжирования в ИПС 93
3.1 Организация ранжирования и архитектура ИПС 93
3.1.1 Факторы ранжирования как исходные критерии оценки релевантности документов при Интернет - поиске 93
3.1.2 Алгоритм синтеза параметров нейросетевого блока ранжирования в ИПС 97
3.2 Структурная схема ИПС с блоком нейросетевого ранжирования 100
3.2.1 Общая структурная схема ИПС 100
3.2.2 Структурная схема блока нейросетевого ранжирования 102
3.3 Архитектура и программная реализация ИПС для Интернет - поиска 103
3.3.1 Архитектура программных средств нейросетевого блока ранжирования 104
3.3.2 Алгоритмы ранжирования на основе сортировок 107
3.4 Выводы 111
4 Экспериментальные исследования характеристик нейросетевого блока ранжирования 112
4.1 Условия экспериментов и особенности применения алгоритмов 112
4.1.1 Особенности организации нейросетевого ранжирования для задач Интернет - поиска большой размерности 112
4.1.2 Показатели эффективности использованных алгоритмов нейросетевого ранжирования в ИПС 116
4.2 Результаты экспериментальных исследований разработанных моделей и алгоритмов ранжирования 120
4.2.1 Оценка качества ранжирования 120
4.2.2 Оценка параметров НС блока ранжирования при Интернет - поиске 122
4.2.3 Экспертное определение эффективности разработанного алгоритма 127
4.3 Сравнительная оценка производительности нейросетевого блока ранжирования ИПС Интернет-поиска 130
4.3.1 Исследование последовательной динамики нейросетевого блока при ранжировании Интернет-ссылок 132
4.3.2 Исследование параллельной динамики нейросетевого блока при ранжировании Интернет-ссылок 133
4.4 Выводы 137
Заключение 139
Список использованных источников 141
Приложение 1. Фрагмент кода программы, реализующий разработанные алгоритмы 146
Приложение 2. Акт о проведении комплексных испытаний программного продукта «ИПС с ранжированием на основе динамических НС с БФВ» 158
Приложение 3. Свидетельство о государственной регистрации программы для ЭВМ 159
- Цели и задачи дискретных оптимизационных задач и их вычислительная сложность
- Синтез архитектуры и параметров нейронной сети Хопфилда с бинарной функцией выхода
- Факторы ранжирования как исходные критерии оценки релевантности документов при Интернет - поиске
- Показатели эффективности использованных алгоритмов нейросетевого ранжирования в ИПС
Введение к работе
Актуальность проблемы. В процессе развития Интернета и роста объемов данных локальных вычислительных сетей вероятность существования нужной информации растет, а возможность ее нахождения уменьшается. Надлежащий поиск необходимой информации становится общей проблемой. Требуются новые методы и инструментальные средства, решающие проблемы релевантного поиска в чрезвычайно больших объемах информации.
Целью разработчиков информационно-поисковых систем (ИПС) является предоставление пользователю документов, в максимальной степени соответствующие смыслу запроса (обеспечить релевантность – точность поиска), при этом, вернуть как можно большее число документов, содержащих запрашиваемую информацию (обеспечить полноту поиска).
Число найденных документов в списке при поиске по ключевому слову можно уменьшить, если продолжить поиск, но уже среди этих найденных документов (ряд поисковых программ предоставляют такую возможность), используя в качестве запроса другое ключевое слово. Увеличение количества ключевых слов и продолжение процедуры поиска в найденных документах, позволяет уменьшить число найденных документов до разумного значения, при котором просмотр текста документов на интересующую тему оказывается уже реальным. Однако, правильный выбор достаточного количества ключевых слов, а еще лучше словосочетаний, представляет определенную сложность, особенно при работе с незнакомым материалом.
Все это обусловливает низкую адекватность найденной по запросу пользователя информации, то есть возврат системой большого объема малоинформативных документов. Проблема может усугубляться низкой скоростью получения документов из Интернета, необходимостью просмотра пользователем всех найденных документов и оценки их информационного содержания в неавтоматизированном режиме.
Альтернативой вторичным процедурам поиска может служить разработка быстрых алгоритмов выбора и сортировки возвращенных документов в соответствии с функциями значимости информационных ресурсов и релевантности документа запросу. Задача оптимального представления ограниченного набора документов из некоторого множества найденных с целью максимизации суммарной релевантности запросу, в данной работе представлена задачей комбинаторной оптимизации.
Объект исследования: сфера интеллектуального поиска текстовой (ссылочной) информации.
Предмет исследования: математическое и программное обеспечение информационно-поисковой системы, в условиях быстрого выбора и сортировки возвращенных документов в соответствии с функциями значимости информационных ресурсов и релевантности документа запросу.
Требования по оперативности и размерности решения задач выбора и сортировки документов привели к необходимости оптимизации в нейросетевом базисе.
Цель диссертационной работы – исследование процесса ранжирования найденных документов по критериям релевантности запросу для повышения достоверности и оперативности функционирования информационно-поисковых систем на этапе предварительного отбора тестовых документов, содержащих формальные признаки наличия интересующей информации.
Для достижения поставленной цели в работе сформулированы и решены следующие задачи.
-
Анализ существующих информационно-поисковых систем и проблем интеллектуального поиска текстовой информации.
-
Анализ методов решения дискретных задач оптимизации, применимых в алгоритмах информационно-поисковых систем.
-
Исследование теоретических основ метода оптимального ранжирования найденных документов, на основе нейросетевых решений задач целочисленного программирования.
-
Разработка модели и метода оптимального ранжирования найденных документов, на основе динамических нейронных сетей Хопфилда с бинарной функцией выхода.
-
Разработка алгоритма функционирования нейросетевого блока ранжирования при различных оценках критерия значимости в ИПС Интернет – поиска.
-
Разработка элементов программного комплекса реализующего алгоритмы оптимального ранжирования документов и ссылок в ИПС.
-
Экспериментальное исследование процессов функционирования блоков ранжирования в соответствии с разработанными алгоритмами.
Методы исследования: теоретические исследования проведены с использованием методов системного анализа, математического программирования, оптимизации, моделирования, алгоритмизации, теории нейронных сетей. Экспериментальная часть работы основана на методах машинного моделирования и вычислительного эксперимента с использованием языков программирования высокого уровня и системы математического моделирования MatLab.
Научная новизна. На основе работ проф. Ю. П. Зайченко выведен ряд аналитических зависимостей, позволяющих сконструировать исходную энергетическую функцию НС Хопфилда с бинарной функцией выхода для оптимального (квазиоптимального) решения задачи векторного ранжирования задач большой размерности при Интернет-поиске. В отличие от ранее известных, в выражении для энергетической функции сети умышленно опущен временной параметр в связи с тем, что при определении синапсов и внешних смещений он не играет какой-либо существенной роли как для сетей с дискретным временем, так и для сетей с непрерывным временем. Также отсутствует последнее слагаемое, так как оно не зависит от состояния сети. Построен алгоритм функционирования нейросетевого блока ранжирования на основе НС Хопфилда. Экспериментальные исследования выявили, что для эффективного решения задач ранжирования ссылок необходимо обеспечить заданное число нейронов в модели, при котором не превышена верхняя граница локальных минимумов энергетической поверхности сети.
Практическая ценность. Впервые искуственная нейронная сеть интегрирована в информационно-поисковую систему. Разработанная система может быть применена во всех направлениях деятельности человека, где необходим оперативный и качественный поиск информации, например, образование, коммерческая деятельность и информационно-справочного обеспечения. На основе разработанных в диссертации модели, метода, алгоритма, информационно-поисковая система внедрена в практику в ООО инновационная компания «Осанна». По результатам проделанной работы получен акт внедрения и свидетельство об официальной регистрации программы для ЭВМ.
Апробация работы. Основные положения работы докладывались и обсуждались на Всероссийских научных конференциях, в том числе: на III и IV Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» (Краснодар, 2006 – 2007 гг), а также на XIV Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар, 2008 г.)
По теме диссертации опубликовано 8 печатных работ, их них 1 – в периодических изданиях, рекомендованных ВАК России для публикации научных работ, получено 1 свидетельство об официальной регистрации программы для ЭВМ.
Основные положения, выносимые на защиту:
метод ранжирования ИПС Интернет – поиска на основе решений задач комбинаторной оптимизации в нейросетевом базисе.
модель оптимального ранжирования документов в ИПС при векторной и скалярной оценке релевантности на основе динамической сети Хопфилда с бинарной функцией выхода.
структура и алгоритм функционирования блока ранжирования при векторной оценке релевантности на основе нейросетевого решения задачи о назначениях.
структура и алгоритм функционирования блока ранжирования при скалярной оценке релевантности на основе нейросетевого решения задачи сортировки.
архитектура высокопроизводительного нейросетевого блока ранжирования в составе перспективной ИПС Интернет – поиска.
Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 55 наименований и 2 приложения на 13 страницах. Объем основного текста составляет 155 страницы машинописного текста, в том числе 23 рисунков и графиков, 11 таблицы.
Цели и задачи дискретных оптимизационных задач и их вычислительная сложность
Формализация той или иной задачи оптимизации, в общем случае, предполагает описание всех важных факторов, влияющих на достижение цели, их взаимодействия, ограничительных условий и критерия оценки качества принимаемого решения, на основе которого можно осуществлять выбор между альтернативами. В качестве критерия оценки выступает целевая функция, аргументами которой являются количественные характеристики, описывающие состояние факторов, влияющих на достижение цели в решаемой задаче [3]. При этом решению, приводящему к наилучшему результату, как правило, соответствует экстремальное значение целевой функции, то есть точка её максимума или минимума. Следовательно, процесс генерации вариантов решений и выбора наилучшей из полученных альтернатив сводится к созданию всех возможных комбинаций значений характеристик, влияющих на целевую функцию, и нахождение такой комбинации, которая приводит к её экстремальному значению. Все возможные комбинации аргументов при этом образуют пространство поиска задачи Q, размерность которого определяется числом аргументов целевой функции. А каждая из указанных комбинаций образует точку в данном пространстве.
Следует отметить, что целевая концепция при постановке задачи выбора может находить отражение как при задании множества допустимых альтернатив, так и при формулировке требований получения эффективных, в частности, строго оптимальных решений.
Таким образом, целью оптимизационной задачи как практического, так и теоретического характера является выбор "наилучшей" (допустимой или оптимальной) конфигурации из множества альтернатив для достижения некоторой поставленной цели. При этом "наилучшей" понимается в смысле обеспечения оптимума (максимального или минимального значения в зависимости от конкретной постановки задачи) заданной целевой функции при удовлетворении определённым ограничениям. Для дальнейшего упрощения оптимизацию будем понимать в смысле минимизации целевой функции на множестве допустимых альтернатив (например, максимизации суммарной релевантности списка найденных документов в соответствии с множеством заданных критериев).
Все задачи математического программирования разделяют на классы по двум основным признакам: по типу параметров х и по типу функции стоимости и ограничений. По первому признаку задачи оптимизации делятся на два класса: задачи с непрерывными переменными и задачи с дискретными переменными. По первому признаку задачи математического программирования разделяют на следующие классы. Если все или одна из функций fix), (pi(x), \\ft(x) нелинейные, то такая задача относится к классу задач нелинейного программирования. Когда функция fix) выпукла, функции (р/(х) -вогнуты и \\i,(x) - линейны, получаем задачу, называемую задачей выпуклого программирования, которая обладает тем удобным свойством, что из локальной оптимальности её решения следует оптимальность глобальная. Кроме того, для неё имеются достаточные условия оптимальности — условие Куна-Таккера [9]. Наконец, предполагая, что все функции fix), (pj(x), ц/,(х) линейны, получаем класс задач линейного программирования.
Особый интерес представляют задачи дискретного программирования. Среди них выделяют задачи целочисленного программирования, в которых к параметрам предъявляется требование целочисленности.
Из всего многообразия типов задач математического программирования выделяют задачи, в которых множество допустимых альтернатив конечно или бесконечно, но счётно, при этом строится данное множество по тем или иным правилам комбинаторики. Такие задачи составляют класс задач комбинаторной оптимизации. Комбинаторный характер имеют задачи линейного программирования, так как любая из них сводится к выбору решения из конечного множества возможных, представляющих множество вершин выпуклого многогранника, определяемого линейными ограничениями. К задачам комбинаторной оптимизации относятся задачи целочисленного программирования.
Так как задачи комбинаторного программирования сводятся к выбору на конечном множестве альтернатив, то в принципе каждая подобная задача может быть решена методом полного перебора. Естественным является постановка вопроса о трудоёмкости алгоритмов, реализующих этот метод. Эта трудоёмкость определяется в основном мощностью исходного множества альтернатив [28,33].
В задачах программирования с булевыми переменными, в которых размерность вектора параметров х равна п, а элементы вектора х могут принимать значения {0,1}, мощность множества альтернатив будет А=2". Число шагов вычислительного процесса при реализации алгоритма полного перебора и соответственно эффективность данного алгоритма также определяется числом 2". Про такие алгоритмы говорят, что они имеют экспоненциально возрастающую трудоёмкость, более точно - экспоненциально возрастающую трудоёмкость с базисом равного 2. В случае, если элементы вектора параметров х могут принимать значения х,е{0,1,2,3...., А:-1}, получаем мощность Л=" и, следовательно алгоритм полного перебора имеет экспоненциально возрастающую трудоёмкость с базисом к. Для таких алгоритмов увеличение числа п в два раза ведёт к возрастанию А в квадрате. Алгоритмы, трудоёмкость которых возрастает в зависимости от размерности п более быстро, чем по экспоненте, также относят к классу алгоритмов с экспоненциальной трудоёмкостью, их можно также назвать суперэкспоненциальными алгоритмами. Таким образом, в задачах принятия комбинаторных решений применительно к сложным оптимизационным задачам, для которых характерна большая размерность исходных данных, возможности полного перебора весьма ограничены.
Возникает задача алгоритмической разрешимости - доказательства существования алгоритма существенно более экономичного чем перебор. Стало общепринятым считать переборную задачу решаемой эффективно, если имеется алгоритм, решающий её за время, ограниченное полиномом от размера задачи х.
Анализ трудностей, встретившихся на пути создания эффективных методов решения дискретных задач, привёл к постановке проблемы всей дискретной математике - можно ли исключить перебор при решении дискретных задач? Другими словами, речь идёт о принципиальной возможности найти нужное решение (например, оптимальное), не перебирая всех или почти всех альтернатив в задаче. Различные алгоритмы имеют различную временную сложность, и выяснение того, какие алгоритмы "достаточно эффективны", а какие "совершенно неэффективны", всегда будет зависеть от конкретной ситуации.
В процессе вычислений важно не, только построение алгоритма, но и оценка возможности его реализации. Для этого оценивается:
1) объём памяти, занимаемый алгоритмом;
2) зависимость объёма памяти, занимаемой промежуточными данными, от объёма исходных данных;
3) зависимость времени вычислений от объёма исходных данных.
Основной характеристикой алгоритмов является последняя арактеристика. Под вычислительной сложностью алгоритма (задачи) понимается функция S(n), сопоставляющая каждому набору исходных данных п некоторое абстрактное время его вычисления (решения задачи). Очевидно, что реальное время вычисления алгоритма зависит от типа вычислительного устройства, способа программирования и профессионализма программиста. Однако учёт всех этих факторов можно осуществить с помощью введения соответствующего коэффициента пропорциональности. Для получения временных оценок алгоритма, инвариантных к типу вычислителя часто вводят понятие элементарной операции (сложение, пересылка регистр-регистр). В этом случае время вычисления алгоритма может быть оценено функцией 0(п), которая определяет число элементарных операций от объёма исходных данных п. Построение функции 0(п) позволяет в дальнейшем оценивать реальное время выполнения алгоритма для конкретного вычислителя путём умножения количества элементарных операций на время выполнения отдельной операции. Функцию S(ri) в явном виде удается построить далеко не всегда, однако зачастую можно получить верхнюю S(n) и (или) нижнюю S(n) её оценки, S(n) S(n) S(n).
Синтез архитектуры и параметров нейронной сети Хопфилда с бинарной функцией выхода
Рассмотрим нейросетевую интерпретацию задачи ранжирования по множеству критериев как задачи о назначениях, при условии сведения задачи о назначениях к стандартной форме (число групп критериев равно числу ранжируемых документов) [2 8].
Определим архитектуру нейронной сети, решающую задачу (2.2).
Введем в рассмотрение сеть бинарных нейронов, представляющую собой матрицу размерностью ПУЛ, где п = N — М - число документов или групп критериев.
За основу модели ранжирования может быть взята нейронная сеть (рисунок 2.3), содержащая произвольные обратные связи, по которым переданное возбуждение возвращается к данному нейрону, и он повторно выполняет свою функцию [6,21,32,42].
В динамических нейронных сетях неустойчивость проявляется в блуждающей смене состояний нейронов, не приводящей к возникновению стационарных состояний. В общем случае ответ на вопрос об устойчивости динамики произвольной системы с обратными связями крайне сложен и до настоящего времени является открытым [7,36,49].
Пусть используемая дискретная сеть Хопфилда имеет следующие характеристики (рисунок 2.3):
1. Один слой элементов (входные элементы, представляющие входной образец, не учитываются).
2. Каждый элемент связывается со всеми другими элементами, но элемент не связывается с самим собой.
3. За один шаг обновляется только один элемент.
4. Элементы обновляются в случайном порядке, но в среднем каждый элемент должен обновляться в одной и той же мере (частоте).
5. Вывод элемента ограничен значениями 0 или 1, т.е функция выхода бинарная [6].
Сеть Хопфилда является рекуррентной в том смысле, что для каждого входного образца выход сети повторно используется в качестве ввода до тех пор, пока не будет достигнуто устойчивое состояние.
Соответствующим образом организованная (запрограммированная) неиросеть после "запуска" меняет свое состояние, постепенно переходя в установившийся режим.
По данному режиму идентифицируется результат - план оценивания документов множеством групп критериев, который может не совпадать с точным решением.
Для уточнения результата обычно используются процедуры случайного поиска [36].
Удобно считать, что сеть Хопфилда не имеет входных элементов, так как входной вектор просто определяет начальные значения активности элементов. Элементы обновляется тогда, когда все элементы передадут свои значения активности по имеющимся взвешенным связям, после чего вычисляется сумма произведений (т.е. берется скалярное произведение).
Значение активности элемента получается на основе использования некоторого правила активизации.
В данном выражении для энергетической функции сети умышленно опущен временной параметр в связи с тем, что при определении синапсов и внешних смещений он не играет какой-либо существенной роли как для сетей с дискретным временем, так и для сетей с непрерывным временем. Более того, данным выражением мы будем пользоваться при определении параметров синтезируемых сетей, как с дискретными, так и с непрерывными состояниями. Основанием для этого служит тот факт, что энергетические функции сетей с дискретными и с непрерывными состояниями отличаются только наличием у последних интегрального слагаемого, которое ни от значений синапсов, ни от внешних смещений в явном виде не зависит.
Сопоставление линейных членов позволит определить значения внешних смещений, а сопоставление квадратичных членов позволит определить синаптические связи между нейронами.
Анализ первого слагаемого сконструированной энергетической функции свидетельствует о том, что любой нейрон сети должен иметь синаптические связи с коэффициентом -А со всеми нейронами одноименной с ним строки (условие ju= і) кроме самого рассматриваемого нейрона (условие уф]).
Второе слагаемое диктует наличие связей с коэффициентом -В между нейронами одноименного столбца (условие v=j) кроме собственной обратной связи (условие /иф І).
Третье слагаемое свидетельствует о том, что все нейроны сети связаны друг с другом синапсами с коэффициентами -С. Воспользовавшись символом Кронекера Sp, запишем результирующее выражение для синаптических связей сети в виде.
Как правило, в практических задачах принимают F =1 и А = В, тогда все ненулевые связи имеют одинаковый вес, равный -А. Кроме того, анализируя выражения (2.23) и (2.24), можно заметить, что наличие глобальных связей с коэффициентом -С каждого нейрона с каждым в конечном состоянии сети, соответствующем некоторому плану назначений, обеспечивает подачу на любой нейрон со стороны всех других суммарного сигнала, равного -Сп, который компенсируется постоянным смещением - Сп. Следовательно, для упрощения структуры синапсов сети глобальными связями с весом -С и частью смещения -Сп в первом приближении можно пренебречь. В этом случае упрощенную структуру сети для синтеза оптимального плана оценивания документов путем решения задачи о назначениях можно представить в виде, изображенном на рисунке 2.5.
Факторы ранжирования как исходные критерии оценки релевантности документов при Интернет - поиске
Реализованные алгоритмы ранжирования являются содержанием четвертого этапа поиска информации. Собственно, весь поиск включает в себя следующие этапы:
1. Формализация пользователем поискового запроса.
2. Поиск и предварительный отбор документов, содержащих формальные признаки наличия интересующей информации.
3. Анализ отобранных документов (лексический, морфологический, синтаксический, семантический).
4. Оценка соответствия смыслового содержания найденной информации требованиям поискового запроса и сортировка в соответствии с со скалярным или векторным критерием релевантности.
На 4-м этапе поиска, все найденные документы dj, j = 1,...,М в соответствии с каждым критерием v„, i=l,...,U обладают некоторой релевантностью ruj, u=\,...,U, j— 1,...,М В свою очередь, на формирование исходных критериев vH, 7=1,..., U влияет три типа факторов:
1. Статические факторы, формирующие агрегированный статический ранг или авторитетность документа, который зависит от количества и ранга документов, ссылающихся на данный документ. Статические факторы измеряют важность или авторитетность страницы, не обращая внимание на ее содержание [41]. Наиболее известным примером реализации статического фактора является показатель PageRank, использующийся в поисковой машине Google. В основу его вычисления положена вероятностная модель пользователя, блуждающего по документам сети. Предполагается, что он с равной вероятностью может перейти по любой ссылке, которую содержит документ [47]. Так же с некоторой одинаковой для каждого документа вероятностью, пользователь может попасть на него не по ссылке с другого документа (например, набрав вручную адрес документа в адресной строке браузера или воспользовавшись "закладкой"). Таким образом, вероятность того, что пользователь посетит конкретный документ, которая и принята за ранг документа PageRank, равна.
2. Динамические внутренние факторы, учитывающие степень соответствия запросу содержимого самого документа [16,41].
Динамические внутренние факторы измеряют собственно релевантность текста страницы, то есть показывают, насколько содержимое самой страницы соответствует определенному запросу. Это наиболее понятные и логичные показатели. К основным страничным факторам относятся:
- внутридокументная частота поисковой фразы;
- элементы форматирования текста;
- вхождение слов запроса в служебные теги и атрибуты.
Общий вклад страничных факторов в итоговое значение релевантности документа запросу усиливается значением статического фактора как весовым коэффициентом. Чем больше статический ранг документа, тем больше эффект от страничных факторов. Это особенно чётко прослеживается при ранжировании документов по низкочастотным запросам, когда влияние динамических внешних факторов стремится к нулю.
3. Динамические внешние факторы, как правило, учитывающие степень соответствия запросу текста ссылок на документ ("ссылочное ранжирование") [41]. Динамические внешние или ссылочные факторы измеряют релевантность ссылок на страницу с других страниц, т.е. показывают насколько соответствующей запросу эта страница считается другими документами.
Влияние конкретной текстовой ссылки на релевантность документа запросу, зависит от нескольких показателей. Один из них - релевантность текста ссылки запросу. Наибольший эффект от текстовой ссылки при ранжировании документа, на который она ведет, по определенному запросу возникает тогда, когда поисковая фраза имеет точное вхождение в её текст. Если же точного вхождения нет, но все слова из поисковой фразы встречаются в тексте ссылки, то эффект от нее при прочих равных будет намного меньше. Если же хотя бы одно слово из поисковой фразы в тексте ссылки не присутствует, то влияние ее может вообще быть равно нулю [54].
В документе [16] даны теоретические аспекты учета различных дополнительных факторов для коррекции релевантности документа запросу. Эти факторы разбиты на несколько категорий [41].
1. Временные данные. Дата регистрации домена, дата первой индексации сайта, документа, динамика изменения документа, данные о переходе пользователей (clickhrough rate) на страницы сайта по ссылкам в результатах поиска и т.п.
2. Информация о входящих ссылках. Динамика появления и изменения ссылок на документ, возраст ссылок на документ, тематика ссылок на документ, процент схожих текстов ссылок на документ и т.д.
3. Информация об исходящих ссылках. Динамика появления и изменения исходящих ссылок, качество и тематика ресурсов, на которые ведут ссылки и т.п.
4. Информация о домене. Дата окончания срока регистрации домена, DNS records, адреса name-серверов, хостинг-компания и расположение хостинга и т.п., динамика изменения этих данных.
5. Информация о ранжировании. Динамика изменений в ранжировании сайта, учет сезонности и "ажиотажности" тематики сайта и т.п.
6. Поведение пользователя. Частота визитов пользователей на страницы сайта и продолжительность проведенного там времени и т.п.
7. Данные, предоставляемые пользователем. Динамика появления страниц сайта в данных, генерируемых пользователями (закладки, кеш и временные файлы браузеров пользователей и т.п.)
8. Тематика документа и др.
Показатели эффективности использованных алгоритмов нейросетевого ранжирования в ИПС
Для оценивания эффективности нейросетевого решения оптимизационных задач ранжирования введен комплексный показатель [20] Ф = (ф,г,фг,Фя), (4.1) где Ф\у - характеризует результативность процесса нейросетевого решения, Фт - оперативность получения искомого решения, Фя ресурсоемкость или структурную сложность реализации нейроподобной сети в блоке ранжирования ИПС.
Показатель результативности EV определяется близостью полученного нейросетевого решения х к строго оптимальному, которое обозначим дгшш. Отметим, что в каждой конкретной постановке оптимизационной задачи значение целевой функции ф(х) определяется не только вектором параметров х, но и конкретным набором исходных данных задачи параметров поискового запроса. Для определенности обозначим набор параметров поискового запроса обозначим как с. Тогда целевая функция решаемой оптимизационной задачи в общем случае будет иметь вид ф(с,х).
В силу того, что различные исходные данные с решаемой задачи будут определять и различные диапазоны значений целевой функции ф(с,х) на множестве допустимых решений Q.x, показатель результативности должен иметь относительный характер. В качестве базы такого относительного показателя необходимо использовать какую-либо характеристику диапазона возможных значений целевой функции. Ниже приведены несколько вариантов показателя результативности. Данный показатель принимает максимальное значение, равное 1, если полученное нейросетевое решение является строго оптимальным. Чем дальше полученное решение от строгого, тем меньше значение показателя (4.3). Оба приведенных показателя результативности нейросетевого решения определены на конкретном наборе исходных данных решаемой оптимизационной задачи с и соответствуют конкретному начальному состоянию сети 0). Для того, что бы найти обобщенную оценку результативности нейросетевого решения оптимизационной задачи, не зависящую от конкретных значений ее исходных данных, т.е. параметров поискового запроса и начального состояния сети, необходимо усреднить показатель Фц{с) по всему множеству исходных данных Q.x и все частные решения получать на независимом множестве начальных состояний сети. В итоге получим показатель результативности в виде [13].
Кроме того, качество решения любой оптимизационной задачи, как правило, зависит от ее размерности, то есть от размерности п вектора переменных х. Следовательно, наиболее общую характеристику результативности нейросетевого решения конкретного типа оптимизационной задачи даст зависимость показателя (4.4) от ее размерности Ф (п).
Прк необходимости ка основе такого показателя можно построить интегральные показатели результативности по всему множеству размерностей задачи типа Интернет-ранжирования, представляющих практический интерес, либо по некоторому множеству типов оптимизационных задач ранжирования.
Оперативность получения нейросетевого решения оптимизационной задачи определяется, в первую очередь, типом динамики сети и характеристиками аппаратных средств ИПС, на которых реализована данная нейросеть. Очевидно, что наивысшие показатели оперативности будут присущи сетям, в которых реализовано максимальное распараллеливание процесса обработки информации. В рассматриваемом случае это сети с дискретным временем, работающие в синхронном режиме, и сети с непрерывным временем.
На этапе, когда конкретный вид реализующей аппаратуры не определен, оперативность нейросетевого решения молено оценить в терминах количества тактов эволюции сети из начального состояния в предельное конечное NTK (ДЛЯ сетей с дискретным временем) или временем переходного процесса в сети ТА: (для сетей с непрерывным временем) [21,51]. Таким образом, в зависимости от типа сети оперативность ее однократного применения будем оценивать показателем Фт = NTK или Фт = Тк В общем случае значение данных показателей будет определяться тремя основными факторами: размерностью задачи п, набором исходных данных с и начальным состоянием сети V \ Для получения интегрального показателя на множестве возможных наборов исходных данных и начальных состояний сети воспользуемся процедурой усреднения, аналогичной (4.4).
При неоднократной реализации процесса эволюции сети и определении искомого решения показатель оперативности Фт(п) увеличивается во столько раз, сколько было обращений к сети.
Структурная сложность сети, характеризующая ресурсоемкость нейросетевого решения оптимизационной задачи Ф , определяется, в первую очередь, размерностью задачи п и оценивается двумя основными показателями: количеством нейронов в сети Nhip) и общим числом синаптических связей Nj{ri). Дополнительным показателем сложности сети, играющим важную роль при рассмотрении технологических вопросов реализации нейросетей, молсет являться плотность синаптических связей.
