«ПРЕДСТАВЛЕНИЯ И ПОИСКА СХОДНЫХ СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ЗАДАЧАХ КЛАССИФИКАЦИИ НА ОСНОВЕ РАССУЖДЕНИЙ ПО ПРИМЕРАМ ...»

НАЦИОНАЛЬНАЯ АКАДЕМИЯ МИНИСТЕРСТВО ОБРАЗОВАНИЯ

НАУК УКРАИНЫ И НАУКИ УКРАИНЫ

МЕЖДУНАРОДНЫЙ НАУЧНО-УЧЕБНЫЙ ЦЕНТР

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И СИСТЕМ

На правах рукописи

СОКОЛОВ Артем Михайлович

УДК 004.8 + 004.032.26

МЕТОДЫ НЕЙРОСЕТЕВОГО РАСПРЕДЕЛЕННОГО

ПРЕДСТАВЛЕНИЯ И ПОИСКА СХОДНЫХ СИМВОЛЬНЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ В ЗАДАЧАХ КЛАССИФИКАЦИИ НА

ОСНОВЕ РАССУЖДЕНИЙ ПО ПРИМЕРАМ

05.13.23 — системы и средства исскуственного интеллекта Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель РАЧКОВСКИЙ Дмитрий Андреевич, доктор технических наук Киев —

ОГЛАВЛЕНИЕ

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

ВВЕДЕНИЕ

РАЗДЕЛ 1. АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ АППРОКСИМАЦИИ СХОДСТВА И ПРИБЛИЖЕННОГО ПОИСКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ

1.1. Рассуждения на основе примеров................. 1.2. Распределенное векторное представление информации..... 1.3. Меры сходства последовательностей............... 1.3.1. Векторные меры....................... 1.3.2. Частотные меры и меры на множествах......... 1.3.3. Расстояния редактирования................ 1.4. Методы аппроксимации и оценки сходства с помощью вложений пространств........................... 1.4.1. Векторные метрики и меры сходства на множествах.. 1.4.2. Расстояния редактирования................ 1.5. Задача поиска приближенных ближайших соседей....... 1.5.1. Локально-чувствительное хеширование и распределенные представления..................... 1.5.2. Решение задачи поиска приближенных ближайших соседей с помощью локально-чувствительного хеширования 1.6. Выводы по разделу 1........................

РАЗДЕЛ 2. РАЗРАБОТКА И ИССЛЕДОВАНИЕ ДЕТЕРМИНИРОВАННОГО МЕТОДА

ВЛОЖЕНИЯ ПРОСТРАНСТВА ПОСЛЕДОВАТЕЛЬНОСТЕЙ С КЛАССИЧЕСКОЙ МЕТРИКОЙ РЕДАКТИРОВАНИЯ В МАНХЕТТЕНОВО ПРОСТРАНСТВО

2.1. Базовые обозначения и определения................ 2.2. Классификация структур графа де Брейна............ 2.2.1. Случай (q, w)-неповторяющихся строк.......... 2.2.2. Случай (q, w)-повторяющихся строк........... 2.3. Нижнее и верхнее ограничение на расстояние редактирования. 2.3.1. Ограничения на расстояние редактирования в пределах одного интервала...................... 2.3.2. Распространение ограничений на расстояние редактирования на несколько интервалов.............. 2.4. Детерминированный метод вложения расстояния редактирования в 1................................ 2.4.1. Нижняя оценка стоимости редактирования........ 2.4.2. Верхняя оценка на расстояние редактирования..... 2.4.3. Объединение оценок.................... 2.5. Численное исследование детеминированного метода вложения 2.5.1. Экспериментальное исследование результатов лемм 2. и 2.8............................. 2.5.2. Экспериментальная база RandomStrings......... 2.5.3. Проверка теоретических ограничений детерминированного вложения........................ 2.6. Выводы по разделу 2........................

РАЗДЕЛ 3. РАЗРАБОТКА РАСПРЕДЕЛЕННЫХ МЕТОДОВ ВЛОЖЕНИЯ РАССТОЯНИЯ

РЕДАКТИРОВАНИЯ И ЭФФЕКТИВНОГО ПОИСКА ПРИБЛИЖЕННЫХ БЛИЖАЙШИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

3.1. Рандомизированные методы формирования векторных представлений для поиска ближайших строк................ 3.1.2. Локально-чувствительная функция для расстояния редактирования........................ 3.2. Решение задачи поиска приближенных ближайших последовательностей с помощью рандомизации детерминированного метода.................................. 3.3. Решение задачи поиска приближенных ближайших последовательностей с помощью разработанной локально-чувствительной 3.3.1. Анализ поиска приближенных ближайших последовательностей на основе предложенной локально-чувствительной 3.4. Распределенные представления последовательностей..... 3.4.1. Метод распределенного представления последовательностей без учета порядка элементов........... 3.4.2. Методы распределенного представления последовательностей с учетом порядока элементов........... 3.4.3. Прореживающее связывание и его связь с разработанной локально-чувствительной функцией......... 3.4.4. Тернаризация и бинаризация рандомизированных представлений на основе локально-чувствительной функции

РАЗДЕЛ 4. АЛГОРИТМИЧЕСКАЯ РЕАЛИЗАЦИЯ И ЧИСЛЕННОЕ ИССЛЕДОВАНИЕ

РАСПРЕДЕЛЕННОГО ПРЕДСТАВЛЕНИЯ И ПОИСКА ПРИБЛИЖЕННЫХ БЛИЖАЙШИХ СИМВОЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

4.1. Экспериментальное исследование вероятности коллизии разработанной локально-чувствительной функции........... 4.2. Поиск приближенных ближайших последовательностей с помощью LSH-леса.......................... 4.3. Методы работы с базами с разной длиной последовательностей 4.3.1. Дополнение последовательностей спецсимволами... 4.3.3. Кластеризация последовательностей по длине...... 4.4. Выбор параметров для обеспечения вычислительной эффективности и точности поиска...................... 4.4.1. Экспериментальное исследование качества кандидатов 4.4.2. Экспериментальное исследование порядка ближайших

РАЗДЕЛ 5. РЕАЛИЗАЦИЯ И ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ РАСПРЕДЕЛЕННОГО ПРЕДСТАВЛЕНИЯ И ПОИСКА ПОСЛЕДОВАТЕЛЬНОСТЕЙ

5.1. Разработка программных средств................. 5.1.2. Программный нейрокомпьютер SNC........... 5.1.3. Специализированные программные системы....... 5.2. Применение в задачах классификации.............. 5.2.1. Исследование поиска дубликатов в текстовых и вебколлекциях.......................... 5.2.2. Обнаружение спама в электронных сообщениях..... 5.2.3. Поиск генов и гиперчувствительных сайтов в последовательностях ДНК...................... 5.2.4. Обнаружение вторжений в компьютерные системы...

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ

– символьные последовательности, строки – размерность распределенных векторов P rob[A] – вероятность события A – число интервалов, где выполняется условие A N [A] – индикаторная функция (равна единице, если условие A [A] выполняется, и нулю в остальных случаях) – операция контекстно-зависимого прореживания над – скалярное произведение векторов v1, v (v1, v2 ) АПНС – ассоциативно-проективная нейронная сеть CDT – context-dependent thinning (контекстно-зависимое CBR – case-based reasoning (рассуждения на основе примеров) kNN – k Nearest Neighbors classier (классификатор k ближайших LSH – locality-sensitive hashing (локально-чувствительное SNC – Software Neuro Computer (программный нейрокомпьютер)

ВВЕДЕНИЕ

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

При решении задач на основе примеров, в базе примеров запоминают данные с сопутствующей информацией, например, известными текстами, спамовыми сообщениями, размеченными генетическими последовательностями, «почерк» пользователей компьютерных систем с известными идентификаторами и др. Для новой входной информации система находит в базе один или несколько сходных запомненных примеров и принимает решения, делает прогнозы и выводы о входных данных, адаптируя к ним знания об имеющихся примерах. (J.G. Carbonell, K. Forbus, D. Gentner, J. Kolodner, C.K. Riesbeck, R.C.

Shank, В.П. Гладун, Н.Г. Загоруйко, Д.А. Поспелов, А.И. Уемов и др.). Этап поиска сходных примеров является центральным в методе рассуждений на основе примеров. Для оценки сходства примеров, имеющих последовательную структуру, часто используют расстояние Левенштейна (классическое расстояние редактирования). Широко известен классический алгоритм вычисления расстояния Левенштейна, сложность которого квадратична относительно длины строк. Однако при больших характерных длинах и количестве примеров последовательностей в базах и во входных потоках непосредственное применение этого алгоритма требует больших вычислительных затрат.

Для повышения эффективности нахождения сходства примеров используют трансформации форм их представления. Ряд подходов к такой трансформации связан с моделированием нейросетевых механизмов структурнофункциональной организации мозга (П.И. Бидюк, Е.В. Бодянский, А.М. Касаткин, Л.М. Касаткина, Н.Н. Куссуль, А.М. Резник, А.А. Фролов, S. Amari, J.

Hopeld, S. Grossberg, T. Kohonen, B. Widrow, D. Willshaw и др.) и распределенного представления информации в мозге (D. Hebb, G. Hinton, P. Kanerva, J.

McClelland, G. Palm, T. Plate, J. Pollack, D. Rumelhart, P. Smolensky, D. Touretzky, Э.М. Куссуль, Д.А. Рачковский и др.). Распределенное представление – форма векторного представления информации, где каждый объект (символ, подпоследовательность, признак, физический объект, их совокупность и др.) представлен множеством элементов вектора, а отдельный элемент вектора может принадлежать представлениям разных объектов. Этот подход тесно связан с подходом вложений пространств (P. Indyk, R. Motwani, A. Broder, C. Sahinalp, G. Cormode, T. Batu, M. Charikar и др.).

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

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

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

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

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

Связь работы с научными программами, планами, темами.

Работа выполнялась в рамках следующих НИР: «Разработка и исследование нейросетевых методов моделирования когнитивных процессов», № ГР 0101U (2001-2003); «Дослiдження та розроблення нових iнтелектуальних iнформацiйних технологiй на основi використання високоефективних нейромережевих методiв та алгоритмiв» № ГР 0102U002070 (2002-2006); «Разработка и исследование нейросетевых информационных технологий работы с базами знаний» № ГР 0104U003191 (2004-2006); «Создать опытные образцы нейрокомпьютеров новых поколений» № ГР 0101U006718 (2000-2001), «Разработать методы и создать способы интеллектуализации информационных технологий широкого использования» № ГР 0101U007953 (2001); «Створити засоби автоматичної обробки iнформацiї iз застосуванням мiркувань за аналогiями», № ГР 0103U008280 (2003-2006), ДНТП «Образный компьютер»: «Розробка технологiї для створення систем смислової iнтерпретацiї текстової iнформацiї та смислового перекладу текстiв з однiєї мови на iншу» № ГР 0102U (2002); «Разработать компьютерную технологию целенаправленной обработки текстовой и аудио информации» № ГР 0103U005770 (2003); »Разработать интеллектуальные информационные технологии распознавания и идентификации аудио-видео-информации на основе нейросетевых технологий» № ГР 0104U008324 (2004).

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

1. Разработать методы векторного представления символьных последовательностей, сохраняющие сходство по расстоянию редактирования.

2. Разработать и теоретически проанализировать методы рандомизированного распределенного представления последовательной информации.

3. Разработать и исследовать методы поиска сходных символьных последовательностей c помощью распределенных представлений.

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

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

Объект исследования: представление и обработка символьных последовательностей в системах поиска и классификации.

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

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

Научная новизна полученных результатов.

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

2. Впервые предложена локально-чувствительная функция, отличающаяся учетом расстояния редактирования между последовательностями, которая продуцирует распределенное представление последовательностей, сохраняющее их сходство по расстоянию редактирования.

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

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

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

• Программная объектно-ориентированная библиотека для представления и поиска последовательностей LSHLibrary, реализующая методы представления и поиска приближенных ближайших символьных последовательной.

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

• Програмные макеты DuplClassier, EmailClassier, NuclClassier, SessionClassier для поиска текстовых дубликатов, спама, кодирующих участков генетических последовательностей и классификации сессий пользователей UNIX-системы.

• Модули программного нейрокомпьютера SNC:

– KNN, реализующий алгоритм поиска K ближайших соседей по заданной метрике;

– VectorComparer – унифицированное средство сравнения векторов по множеству стандартных метрик и мер;

– обрабатывающие блоки – форматирования, предобработки, кодирования и др.

Разработанное алгоритмическое и программное обеспечение используется в научных и практических целях, что подтверждается соответствующими актами: Министерства промышленной политики Украины (от 26.10.05), Института информатики АН Чешской Республики (от 21.11.2005), ТЕЛКО ЛИМИТЕД (от 17.10.2007).

Личный вклад соискателя. В работах, написанных в соавторстве и опубликованных в профильных изданиях, вклад соискателя состоит в следующем: [140] – метод идентификации пользователей с помощью нейронных сетей обратного распостранения ошибки. В [123] – концепция модулей форматированного ввода информации и классификации в нейрокомпьютере. В [107] – прореживающая схема распределенного представления последовательностей и идеи ее анализа. В [132] – поиск текстовой информации с использованием q-граммного представления. В [130] – модули форматированного ввода информации и классификации.

Апробация результатов диссертации. Результаты диссертационного исследования были доложены на: Intern. Joint Conf. on Neural Networks (USA, 2003), X, XI, XII Intern. Conf. «Knowledge-Dialogue-Solution» (Bulgaria, 2003, 2005, 2006); Международной конференции «Проблемы нейрокибернетики»

(Ростов-на-Дону, 2002, 2005); Международном семинаре по индуктивному моделированию (Киев, 2005); Школе-семинаре «О проблемах образного мышления» (Жукин, 2005); семинарах «Проблемы нейрокомпьютеров и нейросетей»

научного совета НАНУ по проблеме «Кибернетика» (Киев, ИПММС НАН Украины и МНУЦ ИТиС НАН Украины, 2001 – 2008) и «Образный компьютер» (Киев, МНУЦ ИТиС НАН Украины, 2008).

Публикации. Основные результаты диссертации изложены в 18 печатных работах, из них 11 – в профильных изданиях Украины и других стран, из них 6 – без соавторов.

АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ

АППРОКСИМАЦИИ СХОДСТВА И ПРИБЛИЖЕННОГО ПОИСКА

ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Задачи обработки и извлечения полезной информации из больших массивов данных, для которых важна последовательность их компонентов, требует повышения эффективности и интеллектуализации соответствующих информационных технологий. Во многих прикладных задачах разных предметных областей существует необходимость сравнения длинных символьных последовательностей. Это поиск в Интернет, обнаружение плагиата, фильтрация дубликатов поисковыми машинами Интернет, системы документооборота. В компьютерных системах и сетях актуальной задачей является обнаружение вторжений, в частности, путем анализа сессий или потока сетевого трафика на предмет наличия аномалий в поведении пользователей. Современные спутники непрерывно генерируют и пересылают измерения, которые также необходимо сравнивать. Одной из самых распространенных современных задач, с которой генетики сталкиваются ежедневно, является поиск близких последовательностей нуклеотидов [77, 17, 144, 104, 79, 51].

Характерные длины последовательностей в этих областях изменяются от 102 -105 (веб-страницы) до 109 (геномы), а количество последовательностей – от 101 -103 (сессии пользователей) до 107 -108 (индекс поисковых машин или база генетических последовательностей).

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

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

Для сравнения последовательностей-примеров в базе необходимо задаться метрикой (ряд метрик рассмотрен п. 1.3), которая должна быть адекватной задаче и эффективно вычислимой. Для сравнения и поиска ближайших среди большого количества длинных последовательностей необходимы эффективные методы. Для этого применяют «сокращенные» представления которые, требуя меньше ресурсов для хранения и обработки, чем исходная информация, сохраняют необходимую для приложений информацию. В п. 1.2 рассматриваются относящиеся к этому типу распределенные представления, развиваемые в области нейросетевого подхода к искусственному интеллекту, а в п. 1.4 – методы теории вложений, позволяющие аппроксимировать сложновычислимые метрики. В п. 1.5 рассмотрены подходы к приближенному поиску ближайших примеров. В п. 1.6 обосновано направление исследований диссертационной работы.

1.1. Рассуждения на основе примеров В системах искусственного интеллекта решение класса задач, связанных с классификацией и поиском последовательностей, возможно с использованием подхода, основанного на моделировании интеллектуальной деятельности человека, а именно рассуждений на основе примеров или прецедентов (CBR – case-based reasoning) [69].

Направление рассуждений на основе примеров является альтернативой типичному для экспертных систем подходу, основанному на правилах [122].

Недостатками подходов, основанных на правилах, являются трудоемкость и высокая стоимость создания, ориентация на специфику предметных областей;

проблемы с обобщением; сложность последовательного поиска в больших системах и др. [89]. Применение CBR-подхода становится еще более актуальным в связи с ростом числа и объемов баз данных и знаний, где хранятся примеры ситуаций и решенных задач, обучающих выборок, и т.п. Разновидность этого подхода – метод ближайшего соседа [38] – широко используется в области классификации и распознавания образов.

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

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

Рис. 1.1. Схема подхода к решению задач на основе рассуждений по примерам 1.2. Распределенное векторное представление информации Моделирование представления информации в мозге является основой нейросетевого подхода к обработке информации. Применение рассуждений на примерах связано с проблемой, состоящей в том, что информация разного типа, модальности, степени сложности обычно представлена в разных форматах, что требует различных средств ее обработки и сильно влияет на эффективность метода в целом. Выбор представления информации определяет возможности и эффективность методов и алгоритмов, применяемых для решения поставленных задач [4, 127, 89].

Перспективными с точки зрения повышения эффективности обработки информации и интеграции информации различных типов являются распределенные представления. Распределенные представления информации (distributed representation) – форма векторного представления, где каждый объект (или единица информации) представлен многими элементами вектора, и каждый элемент вектора может участвовать в представлении многих объектов [111, 115]. В распределенных представлениях состояние отдельных элементов не интерпретируется в отрыве от значений состояний других элементов сети [111].

Нейросетевые распределенные представления обеспечивают параллельную обработку и поиск, хорошую обобщающую способность, поиск по неполным данным и т.п. Преимущества распределенных представлений [91, 111, 89, 138] состоят в:

1. эффективном использовании ресурсов (для представления информации используется ограниченное множество элементов, в то время как в локальных представлениях для представления нового объекта создается новый элемент);

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

3. явном представлении сходства объектов (по мерам сходства соответствующих им векторов);

4. параллельности алгоритмов обработки;

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

Относительно недавно появились модели распределенного представления, которые позволяют представлять и оперировать структурированной информацией (temporal synchrony [102], binary spatter-coding [64], holographic reduced representations [89], ассоциативно-проективные нейронные сети (АПНС) [91]).

В основе работы лежат распределенные представления, развиваемые в рамках парадигмы АПНС [72], истоки которой лежат в работах по моделированию процессов мышления, инициированных Н.М. Амосовым [4]. В АПНС любая информация представления многомерными (бинарными) разреженными псевдослучайными векторами. Под разреженностью понимается малое количество единиц, а под псевдослучайностью – случайность, но неизменность их расположения для представления одной и той же информации. Степень сходства объектов x и y оценивается по мерам сходства их векторных представлений.

Для представления непохожих объектов (различных символов или далеких числовых значений) часто используются независимые случайные векторы [92], каждый элемент такого вектора – независимая и одинаково распределенная случайная величина из {0, 1}. Для представления похожих объектов (близких строк или числовых значений) используются векторы с долей совпадающих единичных элементов, зависящим от степени сходства объектов.

Предложены варианты распределенных представлений и в виде векторов с вещественными элементами [88, 89]).

Представление структурированной информации в виде распределенных векторов требует адекватного учета информации о группировке элементов структуры. Для этого предложен ряд процедур «связывания» [92], которые основаны на избыточности распределенного представления информации.

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

Для двух векторов Xk связывание поэлементной конъюнкцией осуществляется как Z = Xk, k = 1,..., K. Процедура связывания кодвекторов конъюнкцией имеет следующие свойства.

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

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

3. средняя плотность итогового вектора зависит от числа входных векторов K и степени их перекрытия.

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

Аддитивная процедура контекстно-зависимого прореживания CDT (context-dependent thinning) [92] состоит в следующем. Формируется побитовая дизъюнкция связываемых векторов Z = i vi, затем осуществляется контекстнозависимое прореживание с помощью поэлементной конъюнкцией где Zk – перестановка вектора Z. Для каждого k применяется своя случайная независимая перестановка, отличная от вектора Z. Число K – кратность прореживания, определяющая плотность результирующего вектора.

Связывание с помощью CDT [92]:

1. обеспечивает пропорциональное представительство компонентов (подмножество единиц вектора компонента, входящее в состав прореженного вектора, зависит от соотношения плотности данного вектора с векторами других компонентов);

2. сохраняет сходство часть-целое между составными объектами и компонентами, их образующими (в результирующий вектор входят подмножества единиц векторов соответствующих компонентов);

3. сохраняет сходство подмножеств составных объектов (в результирующий вектор входят подмножества единиц векторов соответствующих компонентов, поэтому векторы объектов, содержащие одинаковые компоненты, похожи);

4. обеспечивает структурное сходство составных объектов (состав подмножества единиц для вектора компонента зависит от других векторов, входящих в состав составного объекта) На основе процедур прореживания можно формировать распределенные представления, учитывающие структуру, необходимые для создания вычислительно эффективных и качественно новых методов решения задач обработки структурированной информации [92, 91], в т.ч. последовательностей (п. 3.4.2).

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

1.3. Меры сходства последовательностей Обозначим алфавит символов и две последовательности x, y n.

Под элементами последовательностей xi x, yi y будут пониматься или символы из алфавита, или же (в зависимости от приложения) слова в текстах x, y. Существует ряд мер, определяющих тех или иным способом сходство последовательностей.

1.3.1. Векторные меры Простейшим способом задать сходство между последовательностями x и y являются аналоги векторных метрик, примененные к последовательностям.

Например, обобщенное расстояние Хэмминга определяющее количество неодинаковых элементов в последовательности. Данная метрика не учитывает возможную разницу в количестве различных элементов и их порядок. Однако, несмотря на свою простоту, может применяться для сравнения генетических последовательностей [21]. Аналогично, для цели сравнения последовательностей могут применяться метрики пространств или сравнение частотных моментов (при k = 0 это количество различных элементов в последовательности, при k = 1 – длина последовательности и при k = 2 – т.н. показатель повторяемости (repeat rate)), применяющиеся в базах данных, маркетинге и анализе сетевого трафика.

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

1.3.2. Частотные меры и меры на множествах В области Information Retrieval (IR) популярны представления последовательностей (текстов) типа «bag-of-items», где последовательность (текст) x рассматривается как множество X входящих в нее символов или подпоследовательностей (слов). Основываются данные представления на очевидном наблюдении, что похожие (в частности, по смыслу) строки должны содержать много одинаковых или похожих частей.

Для последовательности x создается вектор v(x), где элемент вектора v (x) равен числу вхождений элемента в x или основанной на v (x) величине – частоте элемента или статистической мере tf-idf [97]. Примером подобных векторных представлений является q-граммное расстояние [113, 63], определяемое как манхеттеново расстояние (p -расстояние при p = 1, см. (1.2)) между соответствующими векторами где в качестве элементов последовательности выбраны все подстроки длины q строки x (q-граммы). Например, для слова x = ’vacations’ и q = множество X = {’vac’, ’aca’, ’cat’, ’ati’, ’tio’, ’ion’, ’ons’}.

Связанной с такими представлениями является методология векторных пространств (vector space models, VSM) [96]. В этой методологии слово может абстрактно рассматриваться как набор контекстов, в которых оно встречается.

Каждый контекст представлен множеством слов («bag-of-words»), который является или документом, где встретилось слово, или ближайшей окрестностью слова.

Каждому элементу контекста (тексту или слову) ставится в соответствие случайный вектор (с малым числом +1 и -1). Окончательное представление слова формируется суммированием этих векторов каждый раз, когда слово появляется в корпусе, и может быть проинтерпретировано как распределенное представление документа или термина (п. 1.2) или как рандомизированное уменьшение размерности (п. 1.4.1).

Помимо применения метрик, для оценки (семантического) сходства текстов x, y, представленных векторами «bag-of-items», применяется оценка сходства по величине косинуса [98] угла между соответствующими векторами v(x), v(y):

В Интернете часто применяются меры containment C (степень вхождения одного документа x в y) и resemblance R (сходство документов x и y) между множествами X и Y, определяемые [61, 19] как При этом величина 1 R(X, Y ) является метрикой. Данный виды сходства применяется в Altavista [20], похожие алгоритмы использует Yandex [56], а судя по патенту [90], и Google.

Таким образом, задача оценки сходства между последовательностями в таких представлениях сводится к векторному случаю (п. 1.3.1) или к оценке сходства между множествами X, Y. В пользу частотных представлений говорят экспериментальные свидетельства, что учет только статистики наличия элементов в последовательностях позволяет сохранять сходство между текстами на уровне, достаточном для некоторых приложений [49, 124].

Недостатком подобных представлений является отсутствие учета порядка в последовательности (dH и dlp ) или же его учет лишь в той степени, насколько он учитывается выбором элементов последовательности, из которых строятся соответствующие множества («bag-of-items»).

1.3.3. Расстояния редактирования Во многих приложениях, работающих с последовательными данными, более адекватными являются расстояния редактирования. Наиболее известным является классическое расстояние редактирования Левенштейна [129], определяемое между символьными строками x и y как минимальное количество операций вставки, замены и удаления символов для преобразования x в y. Эти операции интерпретируются в задачах генетики как изменения, происходящие при мутациях и эволюции генов [51], в системах документооборота – как искажения при оптическом распознавании текстов, а также хорошо описывают некоторые способы искажения текстов для несанкционированной рекламы в Интернет [48] и обхода систем обнаружения вторжений в компьютерные системы [108].

Широко известен классический алгоритм вычисления расстояния Левенштейна [149, 119, 51, 150], имеющий для строк длиной n сложность O(n2 ) (п. 1.3.3). Ввиду больших характерных размеров n, большого количества строк и невозможности постоянного доступа к сравниваемым последовательностям в полном объеме, применение этого алгоритма в перечисленных выше областях затруднительно.

В обобщенном (взвешенном) варианте классического определения операциям редактирования (замене, вставке и удалению) присваиваются различные неотрицательные стоимости cchg (, ) – замена символа на, cins () – вставка символа, cdel () – удаление символа. Для простоты примем, что эти операции удовлетворяют неравенству треугольника, иначе описанный ниже алгоритм сильно усложняется [150]. Преобразование : x y можно представить как последовательность операций редактирования = 1,..., N, j {chg, ins, del}. Стоимостью некоторого преобразования c( ) называется сумма входящих в него стоимостей каждой операции редактирования: c( ) = j c j.

Под расстоянием редактирования ed(x, y) понимается минимальная стоимость последовательности операций редактирования (замены, вставки и удаления), переводящая x в y:

В классическом варианте определения расстояния редактирования все стоимости равны единице независимо от символа.

Несмотря на то, что время вычисления ed(x, y) полиномиально, существует необходимость ускорения его вычисления для длинных строк. На сегоn дня лучшим временем точного его вычисления – O( log n ) – обладает алгоритм из [76], что лишь немногим лучше оценки для классического алгоритма.

Отметим, что расстояние Хэмминга (1.1) является также расстоянием редактирования (определенной для строк одинаковой длины) с единственной допустимой операцией – заменой, и поэтому dH (x, y) ed(x, y). Существуют другие варианты определения расстояния редактирования, отличающиеся множеством допустимых операций. Например, расстояние редактирования с дополнительной операцией транспозиции смежных символов [33] (частый вид ошибок при наборе с клавиатуры) и длина наибольшей общей подпоследовательности (LCS) (расстояние редактирования с разрешенными только вставками и удалениями), также имеющее квадратичную сложность вычисления [118].

Связанными задачами, основанными на взвешенном расстоянии редактирования, являются задачи поиска глобального [84] и локального [103] выравнивания в генетике, в том числе среди многих последовательностей [51]. Решения всех упомянутых вариантов основываются на динамическом программировании и поэтому полиномиально разрешимы (за квадратичное время).

Более общими и в некоторых приложениях (например, генетика) более адекватными являются расстояния редактирования, включающие помимо символьных операций также и операции над блоками символов. Так, операции копирования, перемещений и удаления (иногда только повторяющихся) блоков символов (а также иногда и изменение порядка символов в блоке), также являются и более общим описанием преобразований, часто встречающихся при мутациях генов [51].

Первоначально вариант блочного расстояния редактирования (не являющегося метрикой) был предложен в [112]. Он представляет собой количество участков текста x, из которых может быть составлен текст y и вычисляется жадным алгоритмом. Варианты определения блочного расстояния редактирования включают LZ-расстояние (не метрика) и расстояние сжатия [31], а также расстояние редактирования с блочными перемещениями [30] и другие [75].

Точное вычисление общих вариантов расстояния редактирования с блочными операциями, как правило, NP полное [75, 101], в то же время они допускают очень эффективные аппроксимации [80, 31, 30, 27].

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

1.4. Методы аппроксимации и оценки сходства с помощью вложений пространств Одним из способов преодоления недостатков трудновычислимых метрик и больших размерностей является изменение исходного пространства на более простое, где задача может быть решена легче. Под целевыми пространствами чаще всего понимаются векторные (или даже R1 [37]), желательно небольшой размерности и, если возможно, с простой метрикой типа 1 из (1.2), или хэмминговой (1.1). Как и в случае использования векторных расстояний для сравнения последовательностей (п. 1.3), это объясняется тем, что в векторных пространствах существует множество алгоритмов для разных задач (k ближайших соседей, классификации, кластеризации и т.д.), а также тем, что для векторов меньших размерностей требуется меньше ресурсов. Кроме того, изменение исходного пространства может быть необходимо из-за невозможности точно посчитать исходную метрику (см. п. 1.3.3). Такое отображение X Y из исходного пространства в целевое называется вложением [57]. Если оба пространства метрические, то такое вложение называется переключением метрик, если метрика одинаковая, но уменьшается размерность – уменьшением размерности.

Вложения используются в различных прикладных задачах [57]. Текущие приложения включают экономную передачу и сжатие данных [31, 27], фильтрацию дубликатов в Интернет [19], сравнение и объединение записей в базах данных [28, 2, 24], сравнение XML-структур [43], генетику [21, 52]. Интуитивно, вложение должно «близкие» элементы в исходном пространстве отображать в «близкие» в целевом, «далекие» – в «далекие». Формально качество аппроксимации вкладываемой метрики оценивают с помощью понятия искажения. Если существует такое c 1, что где d и d – метрика соответственно целевого и исходного пространств, то оно называется искажением вложения [57].

Более слабым определением является понятие порогового (r1, r2, r1, r2 )вложения:

Если (1.8) или (1.9) выполняются с некоторой вероятностью, то они называются рандомизированными вложениями.

1.4.1. Векторные метрики и меры сходства на множествах Известным результатом является лемма Джонсона-Линденштрауса [62, 60, 34, 57], которая говорит о возможности вложения векторов из 2 размерности m в 2 размерности m < m, при только лишь небольшой потере точности:

существует рандомизированное вложение A : m m с искажением c = 1+ и вероятностью ошибки = e(m / ). Вложение A линейно, и его матрица содержит независимые и одинаково распределенные элементы из нормального распределения N (0, 1).

Таким образом, компоненты вектора-образа v l2 получаются следуюm щим образом:

где vj – компоненты исходного вектора v l2, а aij N (0, 1) – элементы матрицы A. При уровне ошибки размерность целевого пространства составляет m = O( 12 log( 1 )). Вместо распределения N (0, 1) можно выбирать элементы матрицы A из множеств {1, 1} (равновероятно) или {1, 0, 1} (p(1) = p(1) = 1/6, p(0) = 2/3) при неизменном искажении c [1].

Для пространства 1 показана невозможность подобного вложения [18] – т.е. уменьшение размерности для M точек в 1 с искажением c требует размерности порядка M (1/c ) (см. также в [59] слабый вариант уменьшения размерности в 1 ). Однако для 1 существует [59] возможность создания векторов v размерности m = O( 12 log( 1 )) аналогично формуле (1.10), но с элементами aij из распределения Коши p(x) = (1+x2 ). Тогда Если вместо распределения Коши (1-стабильное распределение) взять другое p-стабильное распределение, то аналогичным способом можно добиться [29] аппроксимации p метрик (1.2):

где B(p) – определенный коэффициент.

Другие способы аппроксимации расстояния 1 приведены в [41], 2 и частотных моментов (1.3) – в [3].

Уменьшение размерности в случае метрики Хэмминга (1.1) возможно выполнить в смысле определения (1.9). Для этого в (1.10) операции сложения заменяются на сложение по модулю 2, а элементы бинарной матрицы выбираются из распределения Бернулли с вероятностью единицы, зафиксированной на определенном малом значении. Можно показать [71], что существует такое (r1, r1 (1 ), r, r + 1)-вложение, что (1.9) выполняется с вероятностью 1, размерность целевого хэммингова пространства при этом равна m = O( 2 ).

Вложение меры, связанной с мерой сходства по косинусу (1.5) в хэммингово пространство возможно с помощью метода, предложенного в работе [23].

Из индикаторных функций h(v, r) = [(v, r) 0], где r – случайный m-мерный вектор с ri N (0, 1), составляются бинарные векторы, которые могут быть использованы для поиска приближенно ближайших соседей в хэмминговом пространстве (п. 1.5.1).

Данные вложения и аппроксимации могут быть полезны для простейших способов учета последовательности элементов сравниваемых последовательностей векторными представлениями типа «bag-of-items» (п. 1.3.2).

Для меры resemblance сходства множеств (1.6) существует [19] рандомизированный способ оценки сходства путем своеобразного уменьшения размерности за счет сравнения множеств минимальных элементов случайной перестановки исходных множеств. При этом несмещенной оценкой R(X, Y ) из (1.6) является выражение R(mins ((X)), mins ((Y )), где – случайная перестановка, определенная на X Y, а mins (·) – множество из s минимальных элементов аргумента. Основываясь на таком подходе, в работе [60] предложен способ поиска приближенных ближайших по resemblance множеств (см. также п. 1.5.1).

1.4.2. Расстояния редактирования Идея многих алгоритмов аппроксимации и вложения расстояния редактирования состоит в использовании того наблюдения, что близкие строки содержат много общих подстрок, часто значительно более коротких, чем сама строка. Такие методы часто называются q-граммными методами аппроксимации расстояния редактирования, исследование которых началось с работы [114], где доказана лемма Укконена, утверждающая, что для последовательностей x, y n таких, что ed(x, y) k, выполняется dq (x, y) 2kq, где dq (x, y) – q-граммное расстояние (1.4).

Q-граммные методы основаны, в основном, на использовании числа входящих в строку q-грамм для оценки расстояния редактирования и широко используются для оценки верхней границы на расстояние редактирования в методах приближенного поиска строк, а также для фильтрации [83].

Вложение классического расстояния редактирования является известной открытой проблемой [57, 58].

В работе [5] доказано, что для классического расстояния редактирования искажение c 3/2 для пространства 1. Однако, данный результат не конструктивен в том смысле, что не приведен алгоритма с таким искажением, и даже не доказана возможность его существования. В работе [66] показано, что данные результаты дают лишь теоретические пределы принципиально достижимой точности аппроксимации расстояния редактирования любыми алгоритмами, но не могут дать конкретного алгоритма построения таких вложений.

Используя определение вложения (1.9), переформулируем задачу поиска вложения как поиск таких отображения v(·) и величин d1, d2, k1, k2, что, где d – метрика целевого пространства.

В приложении к вложению расстояния редактирования задача поиска такого вложения называется k1 vs. k2 gapped edit distance problem (GEDP) [10]:

получив на входе 2 строки длиной n, расстояние между которыми или меньше или равно k1 ; или больше или равно k2, решить какой из двух случаев имеет место. Чем меньше разница (k2 k1 ), тем точнее аппроксимируется расстояние редактирования. Например, классический алгоритм динамического программирования решает k vs. k + 1 GEDP.

решает k vs. ((k1 n)2/3 ) GEDP используя объем памяти, независящий от n.

В [11] представлен алгоритм, строящий сокращенные представления строк для оценки расстояния редактирования за время O(nmax(/2,21) ). С их помощью решается O(n ) vs. (n) GEDP. Данный алгоритм не вкладывает строки в векторное пространство, а в качестве сокращенных представлений использует части строк, полученные случайным семплированием входной строки, а также использует наблюдение, что строки, находящиеся на малом расстоянии редактирования, имеют много похожих подстрок в близких позициях.

Наилучшим алгоритмом вложения в векторное пространство на сегодня является алгоритм вложения, приведенный в работе [86], с c = 2O( log n log log n) что лучше, чем O(n ) для любого > 0. Используя этот алгоритм, можно добиться решения k1 vs. k1 2O( log n log log n) память квадратично растет от длины строк, что затрудняет его применение на практике.

В q-граммных методах утверждения о нижней границе вида (1.12) доказываются обычно следующим образом:

1. допускается, что ed(x, y) > k2 и d (v(x), v(y)) < d2, где d2 – некоторая величина;

2. используя значение d2, находится для данного случая некоторая (не обязательно оптимальная) последовательность операций редактирования в виде определенного алгоритма и ее стоимость ed(x, y);

3. подбираются параметры так, чтобы ed < k2 ;

4. получается противоречие с ed(x, y) > k2, поскольку по определению ed(x, y) ed(x, y).

Утверждения о верхней границе (1.11), как правило, доказываются применением леммы Укконена (п. 1.3.3, стр. 29).

В работе [10], на шаге 2, авторы ограничиваются рассмотрением операций редактирования только внутри одного интервала строки. Если две одинаковые q-граммы находятся рядом в двух строках с небольшим сдвигом, то строки редактируются в начале и в конце, чтобы «подогнать» их к друг другу.

Аппроксимация простейшего расстояния редактирования с одной операцией – замены, т.е. расстояния Хэмминга (1.1), путем уменьшения размерности описана в п. 1.4.1.

В работе [30] рассматривается более общее определение расстояния редактирования с дополнительной операцией перемещения произвольных блоков и его вложение в манхетенново пространство с искажением O(log n log n).

В то же время, как указано в п. 1.3.3 точное вычисление этого расстояния является NP-полной задачей.

В работе [12] на основе методики Locally Consistent Partitioning [94] предложен метод аппроксимации расстояния редактирования с коэффициентом min{n1/3+o(1), ed(x, y)1/2+o(1) } за практически линейное время O(n), а также метод вложения пространства строк длиной n с метрикой редактирования в пространство строк n/r, r > 0 с той же метрикой с искажением c = O(r1+o(1) ).

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

1.5. Задача поиска приближенных ближайших соседей Сначала рассмотрим задачу (точного) поиска ближайшего соседа (БС).

Имеется множество X и набор объектов P = {x1,..., xP |xi X} и входной запрос y X, тогда задача БС состоит в поиске хотя бы одного x, такого, что x P, ed(x, y) Существует ряд проблем с поиском точного БС даже в векторных пространствах, получивших условное название «проклятие размерности». Для больших размерностей входного пространствасуществующие алгоритмы точного поиска ближайшего соседа сводятся к линейному поиску по P или требуют экспоненциально большой памяти [16], что часто не оправдано для применения на практике, даже в случае, когда метрика вычисляется просто (в случае вложения в векторное пространство).

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

Задача поиска приближенного ближайшего соседа -БС состоит в поиске такого x P, что x P, ed(x, y) (1 + )ed(x, y). Иначе говоря, необходимо найти строку, находящуюся от запроса не более чем в (1 + ) раз дальше, чем его точный ближайший сосед x.

Определим шар радиуса k, состоящий из объектов, расстояния которых от центра шара t не превышает k: S(t, k) = {x : ed(x, s) k}. Задача -БС сводится [60] к решению задачи (, k)-PLEB (Point Location in Equal Balls), которая формулируется как поиск алгоритма, который для любого запроса 1. если существует x P, такое, что y S(x, k), возвращает YES и любую 2. если y S(x, (1 + )k) для всех x P, возвращает NO;

возвращает или YES или NO.

Таким образом, можно решать задачу -БС с помощью решения задачи (, k)-PLEB. Задача (k1, k2 )-PLEB является вариантом -PLEB задачи и формулируется как поиск алгоритма, который:

1. если существует x P, такое, что y S(x, k1 ), возвращает YES и любую 2. в остальных случая возвращает NO.

1.5.1. Локально-чувствительное хеширование и распределенные В работе [60] предложена схема локально-чувствительного хеширования (LSH) для решения задачи (k1, k2 )-PLEB (вариант задачи (, k)-PLEB) и примененная там для расстояния Хэмминга и меры сходства resemblance (1.6).

В [71] также была предложена похожая схема для расстояния Хэмминга.

Идея использования схемы LSH для поиска соседей состоит в том, чтобы, используя определенное количество некоторых хеш-функций из семейства H, добиться высокой вероятности коллизии (совпадения значений хеш-функций) между близко находящимися объектами, и низкой – для далеких объектов.

Тогда, применяя такое же хеш-преобразование к запросу, мы проверяем, не равен ли вектор g(x) = (h1 (x), h2 (x),..., hK (x)), hi H, составленный из хеш-значений функции, какому-нибудь из ранее посчитанных хеш-векторов объектов из P.

Генерируемые локально-чувствительными функциями векторы g(x) можно рассматривать как распределенное векторное представление объекта x размерностью. Поскольку функции g после выбора из G зафиксированы, то распределенное представление одинаковых объектов будет одинаковым (псевдослучайным), а благодаря локальной чувствительности похожие объекты будут иметь похожие представления.

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

Определение [60]: семейство функций H = {h : X U } (где U – некоторое конечное или счетное множество значений) называется (k1, k2, pI, pII )чувствительным или просто локально-чувствительным, если для любых x, y X и любой независимо и равновероятно выбранной хеш-функции h H выполняется:

Для того, чтобы семейство H было «полезным», необходимо, чтобы выполнялось условие k1 < k2, т.е. «близкая» точка x должны находятся ближе к y, чем точки, считающиеся «дальними», и т.е. «близкие» точки должны вызывать коллизию хеш-функций с большей вероятностью, чем «дальние».

1.5.2. Решение задачи поиска приближенных ближайших соседей с помощью локально-чувствительного хеширования Структуры данных и обработка запроса. На предварительном этапе подготовки структуры для приближенного поиска ближайшего соседа определяется семейство функций G = {g : X U K }, где g(x) = (h1 (x),..., hK (x)), hi H. Всего из семейства G выбирается случайно и равновероятно L штук функций g1,..., gL. Создается также таблица, в ячейку которой заносятся строки x из базы P на основании значения хеш-вектора g(x): каждый объект x попадает в ячейку с идентификатором, равным значению хеш-вектора, посчитанном на ней, а именно (h1 (x), h2 (x),..., hK (x)). Размер таблицы ограничен O(|P |L), кроме того, еще необходимо хранить исходную базу – O(n|P |). Построение таблицы завершено, когда каждая x P занесена в соответствующую ячейку.

Процедура поиска. Для строки-запроса y вычисляются все хеш-векторы gi (y), i = 1,..., L и проверяются соответствующие ячейки в таблице. Если проверяемая ячейка содержит объект x S(y, k2 ), мы возвращаем YES и x.

Если после проверки 2L объектов не было найдено ни одного объекта из P в S(y, k2 ), возвращаем NO.

Условия корректной работы процедуры. В [60] доказывается, что можно добиться выполнения следующих условий с константной вероятностью (большей 1/2), при которых описанная процедура поиска приближенного ближайшего соседа корректна:

1. если существует x S(y, k1 ), то должно выполняться gj (x) = gj (x ) 2. количество коллизий хеш-функций с объектами вне S(y, k2 ) в L проверенных ячейках должно быть меньше 2L:

Увеличение размерности векторов (параметр K) используется для уменьшения вероятности коллизии на точках, лежащих вне S(y, k2 ). Увеличение количества копий (параметр L) необходимо для достижения константной вероятности (> 1/2) события 1. Это достигается это выбором значений K, L.

В теореме Индыка-Мотвани доказано, что, если H является (k1, k2, pI, pII )чувствительным семейством функций, и где тогда алгоритм решения (k1, k2 )-PLEB задачи занимает O(n|P | + |P |1+ ) памяти, использует O(|P | ) вычислений расстояния и O(|P | log p1 |P |) вычислений хеш-функций [60]. Из pII < pI и выражения для следует, что время поиска сублинейно от |P |.

Для реализации описанной процедуры LSH можно использовать модификацию, называемую LSH-лес, которая позволяет находить ближайших соседей без обновления хеш-векторов при изменении размера базы P или параметров k1, k2 [13].

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

Так, в работе [35] для построения локально-чувствительного к p -норме семейства хеш-функций предлагается использовать то свойство p-стабильных распределений [85], что линейные комбинации случайных величин i из этого распределения распределены так же, как и одна случайная величина, умноженная на норму коэффициентов данной линейной комбинации [85]. Поскольку скалярное произведение линейно, то (v1, ) (v2, ) распределено так же, как и v1 v2. Поэтому, если поделить действительную ось на равные промежутки, то интуитивно понятно, что скалярные произведения векторов с близкой нормой на случайный вектор из соответствующего стабильного распределения будут попадать в одни и те же или близкие промежутки, и на этом основании можно построить локально-чувствительное семейство.

В случае p = 1 (1-стабильное распределение), для использования этого свойства хеш-функции задаются в виде где r R – некоторое число, b – равномерно распределенная случайная величина из [0, r], а – вектор элементов из 1-стабильного распределения Коши с плотностью (1+x2 ). Можно показать [35], что для двух фиксированных векторов v1, v2, в зависимости от значения l1 -нормы разности векторов l1, вероятность коллизии хеш-фукции (1.18) равна где f (·) – функция плотности модуля случайной величины, распределенной по Коши. Функция p(c) есть монотонно убывающая функция, поэтому, по определению (1.13), семейство функций (1.18) будет локально-чувствительным и их можно использовать в схеме LSH (п. 1.5.2).

Задача поиска (приближенных) ближайших соседей для последовательностей характеризуется теми же сложностями («проклятие размерности»), что и поиск соседей в векторном пространстве. А именно, для большинства наборов операций редактирования поиск ближайшей последовательности должен использовать или экспоненциальную по длине последовательности память, или линейный поиск по базе (сравнение каждой p P с запросом) [80].

В случае использования простейших векторных представлений для последовательностей существует множество алгоритмов, решающих задачу -БС в случае векторных пространств (например, работы [60, 71] для хэммингова расстояния, [35] для 1, [71] для 2 ). Так, для хэммингова пространства и пространства 1 предложены [60, 35] схемы на основе схемы LSH (п. 1.5.1).

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

Связанной задачей является задача pattern matching – приближенного поиска короткой сроки в длинной строке, для решения которой также может быть использована схема LSH для случая хэммингова расстояния между строками [8, 6].

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

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

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

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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ДЕТЕРМИНИРОВАННОГО

МЕТОДА ВЛОЖЕНИЯ ПРОСТРАНСТВА ПОСЛЕДОВАТЕЛЬНОСТЕЙ

С КЛАССИЧЕСКОЙ МЕТРИКОЙ РЕДАКТИРОВАНИЯ В

МАНХЕТТЕНОВО ПРОСТРАНСТВО

Раздел посвящен разработке методов, направленных на повышение эффективности аппроксимации классического расстояния редактирования последовательностей путем его детерминированного вложения в векторное пространство. На основании математического аппарата графов де Брейна (п. 2.2) и оценок нижней и верхней границ на расстояние редактирования (п. 2.3) разработан и проанализирован метод детерминированного вложения (п. 2.4), улучшающий точность аппроксимации по сравнению с известным методом детерминированного вложения. Результаты анализа проверены путем численных экспериментов (п. 2.5).

2.1. Базовые обозначения и определения Будем обозначать алфавит символов, а множество строк длины n N, заданных над, как n. Символ, находящийся в позиции i строки x, будем обозначать x[i]. Подстроку x[i]x[i + 1]... x[j] строки x будем обозначать x[i, j] и писать x[i, j] x, а диапазоны позиций вида [i, j] назовем интервалами.

Подстроки вида x[i, i+q1], q N называются q-граммами [114], а множество всех q-грамм строки – ее q-спектром. Длину строки x обозначим |x|.

Для x n и q N q-граммным вектором строки будем называть вектор vn,q (x) (N {0})||, где каждой q-грамме q соответствует элемент вектора (vn,q (x)) N {0}, равный числу раз, которое встретилась в x:

стей, будем вместо vn,q (x) писать vq (x) или просто v(x).

Для строк x, y n q-граммным расстоянием dq (x, y), называется манхеттеново расстояние (1 -расстояние) между соответствующими q-граммными Последовательность операций редактирования, которые трансформируют строку x в y, будем называть восстановлением y по x.

2.2. Классификация структур графа де Брейна Графом де Брейна [36, 67, 100] B(; q) для алфавита и параметра 3 называется направленный граф G(V, E), множеству вершин V которого соответствуют все (q 1)-граммы, а множеству дуг E V V – все q-граммы в данном алфавите. Соответствующие дугам и вершинам q- и (q 1)-граммы назовем метками. При этом для символов li дуга с меткой l1 l2... lq соединяет вершины с метками l1 l2... lq1 и l2 l3... lq. Иначе говоря, вершины v и v соединены направленой дугой тогда и только тогда, когда, v = (v ||mod||q1 ) +.

Каждой строке x, |x| q соответствует определенный путь x на графе де Брейна, состоящий из дуг, последовательно соединяющих вершины, метки которых есть последовательно входящие в строку (q 1)-граммы (рис. 2.2).

Рис. 2.1. Пример графа де Брейна B({0, 1}; 4). Путь x, соответствующий строке x = 101000110, выделен жирным

GTGC TGCA

CGTG GTGG 6 TGGCA GGCA

ATGC TGCG GCGT ATGG

1 ATGCGT CGTGG GTGGC TGGCA

ATGCG TGCGT

3 GGCGTG GCGTG 5 CGTGCA

1 ATGGCG 2 TGGCGT CGTGC GTGCA

ATGGC TGGCG GGCGT

1 ATGGCGT 2 TGGCGTG 3 GGCGTGC 4 GCGTGCA

ATGGCG TGGCGT GGCGTG GCGTGC CGTGCA

1 ATGCGTG 2 TGCGTGG 3 GCGTGGC 4 CGTGGCA

ATGCGT TGCGTG GCGTGG CGTGGC GTGGCA

Рис. 2.2. Пример графов B[ATGCGTGGCA, ATGGCGTGCA; q], q = 4, 5, 6. Номер q-грамы в строке указан цифрой над соответствующей дугой Подпутем x пути x будем называть связную последовательность дуг x, соответствующую подстроке x x и обозначать как x x. Путь x, состоящий из двух подпутей x и x, будем обозначать как x = x x.

Для x, |x| q обозначим B[x; q] подграф графа де Брейна, т.е. пересечение графа де Брейна и дуг, входящих в строку, вершинами которого являются все (q 1)-граммы строки x (элементы (q 1)-спектра x), а дуги соответствуют ее q-граммам. Обозначим B[x, y; q] граф, построенный на объединении (q 1)спектров двух строк x, y w одинаковой длины w: B[x, y; q] = B[x; q] B[y; q]. При этом множество вершин объединенного графа есть объединение вершин исходных графов Vx,y = Vx Vy, а множество дуг объединенного графа является мультимножеством, состоящим из всех дуг каждого из исходных графов (рис. 2.2).

Рассмотрим возможные локальные взаимные конфигурации путей x и y на B[x, y; q], соответствующих строкам x, y w.

Строку x, |x| w назывем (q, w)-неповторяющейся, если в любом интервале из w символов все w q +1 штук q-грамм различны. Строку x w, являющуюся (q, w)-неповторяющейся, будем называть просто q-неповторяющейся.

Рассмотрим два случая наличия повторов q-грамм:

Случай I. Обе строки x, y w являются q-неповторяющимися.

Случай II. Хотя бы одна из строк x, y w не является q-неповторяющейся.

2.2.1. Случай (q, w)-неповторяющихся строк Сначала рассмотрим случай I. Если x и y содержат общую q-грамму с метками l1... lq, то соответствующие им пути x и y на B[x, y; q] будут проходить через одну и ту же дугу, соединяющую вершины с метками l1... lq и l2... lq. Левой (вида --) точками ветвления назовем вершины, где пути x и y, соответственно, расходятся после общей дуги или сходятся перед общей дугой.

Например, вершина l2... lq будет правой точкой ветвления, если следующие за ней вершины, принадлежащие x и y, различны: 3... lq lq+1 = (l3... lq lq+1 ) или же один из путей закончился в вершине l2... lq. Аналогично, вершина l1... lq1 – левая точка ветвления, если x и y достигают ее по разным дугам (или для только одного из путей вершина l1,..., lq1 является начальной) и продолжаются дальше по общей дуге l2... lq.

В рассматриваемом случае в B[x, y; q], x = y можно выделить смежные участки вида >--< (если левая и правая точки двух таких смежных конфигураций соединены полупетлей вида >-- |c | > 0, что x = x c x, а y = y c y, где для любых дуг e x x, e y y выполняется условие e = e. Поскольку |x| = |y|, то |x | + |x | = y + y. Подпути x, x, y, y левой или правой вилок, составленые из дуг одной строки, будем называть полувилками. Сдвигом назовем граф, являющийся частным случаем графа-вилки, где левая точка ветвления есть начальной вершиной для одного из путей и правая точка ветвления есть финальной вершиной для другого. Это соответствует ситуации, когда существуют такой общий для x и y подпуть c, w |c | > 0, что x = x c, а akc akcd kcd abc abcd bcd Рис. 2.4. Пример графа B[abcdef ghi, akcdef ght; 4] и двух «вилок». Путь abcdef ghi обозначен сплошной линией и akcdef ght – пунктирной линией y = c y, где e x, e y имеем e = e. Подпути x и y в этом случае будем также называть полувилками. На рис. 2.2.1 вершины cde и f gh являются, соответственно, левой и правой точками ветвления. Правая вилка, обозначена пунктиром и состоит из правой точки ветвления f gh и дуг f ght и ghi, левая – из левой точки ветвления cde и дуг akcd, kcde, abcd и bcde.

При такой конфигурации вилка, связанная с левой точкой ветвления, содержит начальную дугу одного из путей и не содержит дуги другого. А вилка, связанная с правой точкой ветвления, содержит последнюю дугу другого пути и не содержит дуги первого. При этом, одинаковые подстроки x, y, соответствующие пути c, сдвинуты относительно друг друга в x и y на величину Если граф B[x, y; q] является сдвигом, то будем говорить, что x является сдвигом y и наоборот.

На рис. 2.2.1 строка y есть сдвиг x. Путь x обозначен сплошной линией, путь y обозначен пунктирной линией. Подстроке x = cdef ghi, находящейся в обоих строках, со сдвигом, соответствует подпуть x = y = (cde)(def )(f gh)(ghi). Вершины cde и ghi являются, соответственно, левой и правой точками ветвления, вилки (обозначеные пунктирными областями) которых содержат дуги только одного из путей – соответственно, abcd, bcde и ghik, hikt.

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

Рис. 2.5. Пример конфигурации сдвиг графа B[x, y; 4] для x = abcdef ghi, y = cdef ghikt Утверждение 2.1. Если B[x, y; q] является вилкой (сдвигом), то B[x, y; q+ 1] также является вилкой (сдвигом) с тем же количеством дуг в полувилках.

Утверждение 2.2. Если B[x, y; q], x, y n является вилкой с длиной общей части |c |, причем правая вилка состоит из двух полувилок длиной |x | = s1 и y = s2, а левая – с длиной |x | = s3 и y = s4, то для преобразования x в y достаточно выполнить не более min(s1, s2 ) + min(s3, s4 ) операций замены и |s2 s1 | + |s3 s4 | операций вставки или удаления. Так как max(s3, s4 ). Заметим, что верхняя оценка также справедлива для x, y, граф которых не является вилкой, но x и y имеют некоторую общую часть c, а x и y (или x и y ) могут частично совпадать.

2.2.2. Случай (q, w)-повторяющихся строк Случай II. Когда строки не являются (q, w)-неповторяющимися, у одной или обеих подстрок существует хотя бы один подпуть x x (y y ) на графе B[x; q] (B[y; q]), соответствующий подстроке x x (y y), имеющий самопересечение и потому являющийся циклом. Такой цикл имеет хотя бы одну вершину, встречающуюся более одного раза и, поэтому, как минимум одну повторяющуюся (q 1)-грамму. Заметим, что один и тот же цикл может соответствовать разным подстрокам x (y ) – для этого достаточно начать прохождение цикла с другой вершины. На рис. 2.2.2 путь x, соответствующий строке x = abcderstcdef g, обозначен сплошной линией, а путь y, соответствующий строке x = oprstcderstvw, обозначен пунктирной линией. Подстрока x = cderstcde есть вращение подстроки y = rstcderst).

С рассматриваемым случаем II связано понятие вращения [114, 100]. Если записать z l как последовательность (q 1)-грамм:

и если z[1, q 1] = z[l q + 2, l], то вращением называется операция, перевоopr oprs prs prst rst rstv stv stvw tvw Рис. 2.6. Пример графа B[x, y; 4] и общего цикла C, который каждый из путей проходит один раз дящая z в строку z, такую что:

где для некоторого 2 < i < l q непустые подследовательности (q 1)-грамм z[i+1, i+q 1]... z[lq +1, l1] и z[2, q]x[3, q +1]... z[i1, i+q 3] меняются местами. В этом случае говорят, что z является вращением z, и наоборот.

Отметим, что вращением могут быть только строки, у которых совпадают первая и последняя (q 1)-граммы.

Если |x | = |y |, x = y, то при совпадении множеств дуг циклов, соответствующих x и y, эти подстроки являются вращением друг друга.

Следующая лемма утверждает, что при достаточно большом q на B[x; q], где x – (q, w)-неповторяющаяся строка, имеется не более, чем один цикл.

Лемма 2.1. Для x w, q > 2w/3, если существует подстрока x x, такая, что x образует цикл C на B[x; q], то одинаковые дуги вне цикла C отсутствуют.

Доказательство. Пусть f = |x | и подстроки x = x[i, i + q 2], x = x[j, j + q 2], i < j являются парой максимально удаленных среди совпадающих (q 1)-грамм в x. Поскольку q > 2w/3, то эти (q 1)-граммы пересекаются в как минимум 22w/3 w символах и символы подстроки x[i, j 1] будут периодически повторяться подряд в x : если обозначить символы подстроки x[i, j 1] как b1 b2... bB, то x [k] = b((k1) = 1,..., f.

Допустим, совпали две (q 1)-граммы x[i, i + q 2] = x[j, j + q 2], j > i > j, т.е. (q1)-граммы, выходящие своим правым концом за правую границу x. Поскольку q > 2w/3, то эти q-граммы полностью покрывают общий с x и x участок, содержащий как минимум одно вхождение всей последовательности символов b1,..., bB. А поскольку для подстроки x[i, j + q 2] справедливы аналогичные рассуждения про периодический характер (со своей повторяющейся последовательностью), то x[i,j+q2] и x[i,j +q2] проходят те же дуги, что и цикл C. Аналогично рассматривается случай совпадения (q 1)-грамм до x.

Лемма 2.2. Для x, y w, q > 2w/3, если первые (последние) вершины подпутей x x, y y, образующих общий цикл C, не совпадают, то общие дуги x и y перед (после) этими вершинами отсутствуют.

Доказательство. Рассмотрим случай, когда подпути x, y, состоящие из дуг цикла C, оканчиваются в разных вершинах цикла. Пусть x[i, i + q 1] и y[j, j + q 1] – q-граммы, соответствующие последним дугам указанных подпутей в цикле C. Допустим, для i > i, j > j совпали две q-граммы x = x[i, i + q 1] = y[j, j + q 1] = y. Так как q > 2w/3, то они содержат хотя бы одну последовательность символов b1,..., bB из в доказательства леммы 2.1.

Пусть позиции правых концов x[i, i + q 1] и y[j, j + q 1] внутри, соответственно, x и y равны i, j. Поскольку подпути заканчиваются в разных вершинах, а x = y, то i = j.

Поскольку и y, и x составлены из периодически повторяющихся последовательностей символов b1,..., bB, то получаем, что, во-первых, x заканчивается не q-граммой x[i, i + q 1], а x[i + (j i ), i + q 1 + (j i )], и, во-вторых, x и y заканчиваются в одной вершине, что противоречит условию леммы.

Следующее утверждение говорит о характере поведения путей на графах с циклами при изменении q.

Утверждение 2.3. Если для x w существует цикл на B[x; q], q > 2w/3, такой, что в нем присутствуют повторяющиеся дуги, то с каждым увеличением q на единицу длина участка пути между этими вершинами, проходящего более одного раза по одним и тем же дугам, сокращается. При этом общее количество уникальных дуг в цикле не изменяется. Если повторяющиеся дуги в цикле отсутствуют (т.е. каждая дуга цикла присутствует в x ровно один раз), то при следующем увеличении q на единицу цикл пропадает.

Доказательство. По лемме 2.1 цикл единственный. Утверждение можно проверить, проследив на графе B[x; q] с одним циклом изменение количества дуг в цикле и вне его при последовательном увеличении q.

2.3. Нижнее и верхнее ограничение на расстояние редактирования 2.3.1. Ограничения на расстояние редактирования в пределах одного Необходимо найти такое определение расстояния между строками x и y и порог на его значение, чтобы для расстояний меньше этого порога (и при выполнении не зависящих от строк условий на определенные величины) граф B[x, y; q] для случая I содержал бы сдвиг или вилку, и не содержал бы полупетель. Это позволило бы восстановить строки за небольшое число операций (чем меньше это число, тем точнее будет аппроксимация расстояния редактирования), используя утверждение 2.2. Не любое расстояние удовлетворяет этим требованиям: например, при использовании обычного q-граммного расстояния (1 -расстояние между q-грамными векторами) и при фиксированном q для любого допустимого значения q существуют строки x, y, где на графе B[x, y; q] имеется петля. Тогда найти искомый порог не представляется возможным. Пример приведен на рис. 2.3.1, где для строк x = abeeeegh (сплошная линия), y = abeeeghi (пунктирная линия) и графов B[x, y; 3] и B[x, y; 4] значения q-граммных расстояний, соответственно, d3 (x, y) = 2 и d4 (x, y) = 4.

Рис. 2.7. Пример, иллюстрирующий неадекватность q-граммного расстояния для аппроксимации расстояния редактирования В случае I, когда строки являются (q, w)-неповторяющимися, при увеличении q для полупетель и вилок существуют отличия зависимостей числа различных q-грамм. Поэтому для определения различия между полупетлей и вилкой предлагаем использовать следующее расстояние (основанное на обычном q-граммном расстоянии dq ):

определенное для строк одинаковой длины w и фиксированных значений q1, q длины q-грамм. Покажем, что с его помощью можно определить наличие вилки или сдвига, т.е. возможность восстановления пары строк за небольшое число операций редактирования. Случай II наличия повторов q-грамм потребует отдельного рассмотрения (лемма 2.4).

Обозначим q = q2 q1, Q = (q +1)(q +2). Будем называть пару строк x, y плохой, если неравенство d 1,q2 (x, y) < Q не выполняется, и хорошей в противном случае. Покажем, что для хорошей пары строк x, y граф B[x, y; q2 ] является вилкой (или сдвигом).

В следующей лемме рассматривается ситуация, когда для определенных значений q1, q2 (q2 > q1 ) и w строки x, y являются (q1, w)-неповторяющимися и найдем необходимые условия существования петли на графе B[x, y; q2 ] (при этом пара x, y будет плохой). Тогда невыполнение этих условий будет достаточным условием наличия сдвига или вилки при отсутствии общих циклов.

тогда ed(x, y) < 2(q + 1).

Доказательство. Для любой полупетли в графе B[x, y; q], имеющей как минимум по одной общей дуге, находящихся до и после, соответственно, левой и правой точек ветвления, увеличение q на единицу приводит к увеличению на единицу количества дуг в каждой из полупетель, участвующих в формировании петли от каждой строки.

На рис. 2.8 изображено два графа B[x, y; q] и B[x, y; q + 1], где на графе B[x, y; q] имеется петля и левая вилка. При увеличении q на единицу (переходе к B[x, y; q + 1]) узлами B[x, y; q + 1] становятся дуги B[x, y; q], что обозначено пунктирными узлами на дугах B[x, y; q]. Количество дуг в каждой из полупетель увеличивается на единицу по сравнению с B[x, y; q], в то время как количество дуг, формирующих полувилки, не изменяется.

Рис. 2.8. Иллюстрация изменения количества различных дуг в зависимости от конфигурации путей на графе де Брейна Поскольку по определению полупетель в B[x, y; q] дуги одной полупетли не совпадают с дугами из соответствующей ей полупетли другой строки, x[i, i + q 1] = y[i, i + q 1], для всех i таких, что x[i, i + q 1] и y[i, i + q 1] принадлежат своим полупетлям, то тем более не будет совпадений дуг петли в B[x, y; q + 1], т.к. метки дуг в B[x, y; q + 1] содержат метки дуг B[x, y; q] как подстроки: x[i, i + q 1] x[i, i + q] = x[i, i + q 1]x[i + q]. Поэтому для строк x, y, содержащих хотя бы одну петлю, окруженную общими дугами, спрведливо, что общее 1 -расстояние между vq+1 (x) и vq+1 (y) увеличивается как минимум на 2 по сравнению с 1 -расстоянием для предыдущего значения параметра q: dq+1 (x, y) dq (x, y) + 2.

Если же B[x, y; q] является вилкой, то по утверждению 2.1 при увеличении q на единицу они сохранятся и dq (x, y) не изменится. Общее число дуг при этом уменьшается на единицу.

Поскольку при значении q большем, чем половина количества имеющихся в графе B[x, y; q1 ] дуг, ни одна полупетля не сохраняется, для сохранения Учитывая, что минимальное q-граммное расстояние между различными строками равно двум, и при условии, что правая и левая точки ветвления петли не становятся, соответственно, первой или последней вершиной путей в B[x, y; q], при q < q2 (что обеспечивается условием (2.3)), получаем Обратно, если для двух строк x, y w, d 1,q2 (x, y) < Q, то пути на B[x, y; q2 ] не образуют петлю. Тогда соответствующие им пути на графе B[x, y; q] образуют вилку (одностороннюю или двухстороннюю) при некотором q [q1,..., q2 ] и далее при q > q.

Для утверждения, что при d 1,q2 (x, y) < Q не возникает конфигурация вида = (отсутствие совпадающих вершин в путях y и x ) вместо конфигураций сдвига или вилки, должно выполняться условие |c | 1, содержащееся в определении вилки и сдвига, т.е. наличие как минимум одной общей дуги для Если же dq2 1 (x, y) > 2(w q2 + 1) (т.е. нет ни одной общей дуги в B[x, y; q2 1]), то и существует хотя бы одна общая вершина при q = q2.

Таким образом, ввиду наличия петель на графе B[x, y; q] для q = q1,..., q d 1,q2 (x, y) < Q, то, следовательно, петель на B[x, y; q2 ] быть не может, т.е.

B[x, y; q2 ] является вилкой (сдвигом), либо пути на B[x, y; q2 ] имеют конфигурацию вида =. Последнее исключается согласно условию (2.3), как показано выше. Тогда граф B[x, y; q2 ] является вилкой (сдвигом).

По утверждению 2.2 для восстановления вилки при фиксированном q dq (x, y) операций редактирования. Поскольку заранее не известно, при каком значении q = q1,..., q2 образовалась вилка, то можно лишь утверждать, что ed(x, y) dq2 (x, y).

Q, усилим это неравенство. При q2 петли не может быть, т.к. d 1,q2 (x, y) < Q.

Поэтому обозначим как q, q1 q < q2 последнее значение q, при котором Рассмотрим теперь случай II наличия повторов q-грамм. Нас будет интересовать зависимость количества общих дуг на B[x, y; q] у двух путей x и y от q. Отметим, что от случая I будут отличаться только те ситуации наличия циклов, где присутствует совпадение дуг одного пути с дугами другого пути (при этом совпавшая дуга в хотя бы одном цикле встречается больше одного раза) и где уменьшение количества дуг в утверждении 2.3 не компенсирует увеличение расстояния dq (x, y).

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

Лемма 2.4. Пусть при q1 > 2w/3 для строк x, y w существуют такие подстроки x x, y y, x = y, что на графе B[x, y; q] пути x и y состоят из дуг, принадлежащих общему циклу C. Пусть также d 1,q2 (x, y) Q. Тогда ed(x, y) < 2(q + 1).

Доказательство. Допустим от противного, что ed(x, y) 2(q + 1). Покажем, что в этом случае d 1,q2 (x, y) > Q. Найдем минимально возможное значение d 1,q2 (x, y) при заданных условиях леммы. Поскольку характер изw,q менения dq (x, y) при наличии циклов может быть весьма сложным и разнообразным, а получение этой зависимости в замкнутом виде громоздко, для выяснения множества параметров, при которых может реализовываться минимум d 1,q2 (x, y), воспользуемся следующими качественными соображениями, основанными на сравнении зависимостей значений dq (x, y) от характера прохождения цикла обоими путями x, y.

Пусть меньшее число дуг цикла C между вершинами, соответствующими начальным вершинам (первым (q1 1)-граммам) путей x x и y y, равно s. Пусть Lx и Ly – длины подпутей, соответственно x и y, принадлежащих циклу C.

Численно можно построить зависимости dq (x, y ) от Lx и Ly для диапазона изменения s = 0,..., L/2, где L – количество дуг в цикле C (L постоянно, пока цикл существует, по утверждению 2.3). Если длина только одного из путей становится меньше L, то d(x, y ) |Lx Ly |. На рис. 2.9 построена зависимость величины d(x, y) от Lx, Ly для значений s = 0,..., L/2 с учетом приведенных соображений. Видно, что минимальные значения dq (x, y) достигаются при Lx = Ly вне зависимости от s.

Поведение dq (x, y ) в случае наличия одного цикла полностью определяется указанными параметрами s, L, Lx, Ly, пока Lx > L, Ly > L, поэтому можно рассматривать d 1,q2 (x, y ) как функцию от s, L, Lx, Ly. При увеличеw,q нии длины q-граммы (рис. 2.9) dq (x, y ) изменяется вдоль линий постоянного значения величины |Lx Ly | c уменьшением Lx и Ly на единицу. Из характера поверхностей видно, что если Lx < L и Ly < L, то циклы в обоих графах B[x; q] и B[y; q] пропадают, и дальнейшее поведение dq (x, y ) при увеличении q описывается леммой 2.3.

По лемме 2.2 совпадения дуг разных путей вне цикла возможны, если совпадают первые или последние вершины путей x и y. Вклад в dq (x, y) реализуется при s = 0 или совпадении последних вершин x и y ). Поэтому dq (x, y) Можно показать, что сумма вдоль такой линии ряда идущих подряд значений dq (x, y ) для s > 0 будет не меньше, чем для s = 0 для этого же значения |Lx Ly | и в том же диапазоне суммирования q1,..., q2.

Рис. 2.9. Зависимости dq (x, y ) от Lx и Ly для s = 0,..., L, где L = 17. Для иллюстрации белой линией изображено множество точек, где Ly = Lx + Тогда, если (s, Lx, Ly ) = arg mins,Lx,Ly d 1,q2 (s, Lx, Ly ), то d 1,q2 (s, Lx, Ly ) d 1,q2 (0, Lx, Ly ). Поэтому рассмотрим только ситуацию s = 0, когда перw,q вые вершины подпутей x и y совпадают. Случай, когда при этом также |Lx Ly | = 0, рассматривать не будем, т.к. он сводится к отсутствию цикла.

Учитывая, что согласно лемме 2.2 для рассматриваемых конфигураций можно применить утверждение 2.2, получаем, что для |Lx Ly | = max(s1, s2 ) = max(s3, s4 ) должно выполняться |Lx Ly | q +1. Иначе получим ed(x, y) max(s1, s2 ) + max(s3, s4 ) < 2(q + 1), что противоречит предположению в начале данного доказательства. Отсюда Объединим лемму 2.3 с леммой 2.4 и сформулируем лемму 2.5.

Если Q > d 1,q2 (x, y), то ed(x, y) < 2(q + 1).

поэтому значения q могут быть больше или равными единице при w 6. Применяем в случае I (q1, w)-неповторяющихся строк x, y лемму 2.3, в случае II – лемму 2.4.

Мы провели экспериментальную проверку леммы для тех значений параметра w, которые позволяли сделать полный перебор строк на стандартном PC с 1Гб памяти для всех удовлетворяющих условиям леммы значений q1, q из диапазона [3, w]. Для бинарного алфавита полный перебор 2w строк был выполнен для значений w = 4,..., 15 (это заняло около 50 часов). Для тернарного алфавита перебор 3w строк был выполнен для значений w = 7,..., (около 90 часов). Во всех экспериментах не было найдено пары строк, которые бы опровергали утверждение леммы.

2.3.2. Распространение ограничений на расстояние редактирования на Введем понятие хорошего и плохого интервала аналогично понятию хорошей или плохой пары строк. Хорошим интервалом назовем такой интервал вида [i, j], что для пары ограничиваемых им в x и y строк x[i, j] и y[i, j] выполняется d 1,q2 (x[i, j], y[i, j]) < Q (выражение (2.4) при условиях леммы 2.5).

Основной идей, позволяющей нам улучшить предыдущие результаты, является возможность восстановления участков, которые можно рассматривать как сдвиг, малым числом операций, что уточняет нижнюю границу (k2 ) в задаче GEDP (п. 1.4.2).

Ранее [10, 86] возможность восстановления сдвигов не рассматривалась и восстановление происходило по-q-граммно [10], или по-интервально, при выполнении определенных условий [86]. Поэтому, если, например, в одной строке имелся более длинный, чем длина интервала или q-граммы участок, входящий в другую строку в другой позиции, он восстанавливался по частям.

Это приводило к завышению оценки стоимости редактирования и увеличению количества, необходимых для достижения нужной вероятности успеха, итераций вероятностных алгоритмов, основанных на таких вложениях. Отличие разработанного подхода от работы [10] в том, что мы соотносим длинные участки (не покрываемые одним интервалом), совпадающие в обеих строках, то есть те участки, где не применялись бы операции редактирования при преобразовании строк в друг друга. Эти участки могут находиться со сдвигом относительно друг друга. Тогда длинные (превышающие как q, так и w) совпадающие участки могут быть восстановлены за небольшое количество операций в их начале и конце при определенных соотношениях параметров q, w и других.

Далее рассмотрим интервал вида [it +1, it +w], где i – натуральное число из определенного диапазона, т.е. интервалы, взятые с шагом t. Следующая лемма говорит, что возможно «пакетное» восстановление строк, содержащих последовательно идущие хорошие интервалы, для t < t, где t = w q + 1.

выполнении условий леммы 2.5, если для всех i = 0,..., mw выполняется d 1,q2 (x[it + 1, it + w], y[it + 1, it + w]) < Q, то ed(x, y) < 2(q + 1).

Доказательство. Из леммы 2.3 следует, что при отсутствии совпадающих q1 -грамм для каждой пары удовлетворяющих условию леммы 2.5 строк x = x[it +1, it +w] и y = y[it +1, it +w] пути x и y на B[x, y; q2 ] образуют вилку или сдвиг с общим участком пути, состоящим как минимум из w q2 +12q дуг (условие (2.3)) и ed(x, y ) < 2(q +1). Если на интервале [it +1, it +w1] имеются повторяющиеся q1 -граммы в x и/или в y, то из леммы 2.4 следует, что x[it + 1, it + w], y[it + 1, it + w] можно интерпретировать также как сдвиг или вилку (у соответствующих путей есть общий центральный участок дуг длиной как минимум w q2 + 1 2q, различные дуги могут быть только по краям интервала) и что также ed(x, y ) < 2(q + 1).

Рассмотрим два соседних интервала [it +1, it +w] и [(i+1)t, (i+1)t +w].

Поскольку t t 1 = w q, то они пересекаются не менее, чем q символами, что равно максимально возможному размеру полувилки у подпутей, ограниченных хорошими интервалами шириной w.

Правая вилка (сдвиг) на графе B[x[it + 1, it + w], y[it + 1, it + w]; q2 ] и левая вилка (сдвиг) на B[x[(i+1)t, (i+1)t +w], y[(i+1)t, (i+1)t +w]; q2 ], принадлежащие пересечению интервалов, состоят из одних и тех же дуг. Поэтому вариант, когда указанные графы являются вилками с непустыми полувилками (соответственно, правой и левой вилок) или сдвигами на разную величину или в разную сторону, исключается. Следовательно, интервал [it + 1, (i + 1)t + w] весь является сдвигом или вилкой, причем размер сдвига или полувилок так же ограничен сверху q, как и у исходных интервалов. Следовательно, ed(x[it + 1, (i + 1)t + w], y[it + 1, (i + 1)t + w]) 2(q + 1).

Поскольку такие же рассуждения можно распространить на остальные интервалы, то ed(x[1, m], y[1, m]) < 2(q + 1).

Следствие 2.1. Последовательность (при t = 1) из смежных плохих интервалов, окруженная не менее чем одним хорошим интервалом с каждой стороны, состоит из, как минимум, t интервалов.

Доказательство. Пусть t 1, иначе тривиально. Допустим, такая последовательность состоит из t t плохих интервалов, тогда по лемме 2.6 все интервалы между ними должны быть хорошими.

2.4. Детерминированный метод вложения расстояния В этом подразделе на основании утверждений, полученных в подразделах 2.2 и 2.3, получены временные, ресурсные и точностные характеристики детерминированного вложения.